алгебра - Наименьшее число умножений

При самом простом подходе мы можем для нахождения $%x^{16}$% каждый раз домножать на $%x$%, начиная с $%x$%, делая это 15 раз. Однако можно обойтись меньшим числом умножений, если последовательно возводить числа в квадрат. Сначала находим $%x^2=x\cdot x$% (одно умножение). Далее умножаем $%x^2$% на себя (нам это значение известно), и получаем $%x^4$%. Это второе из умножений. При помощи третьего умножения по тому же принципу мы получим $%x^8=x^4\cdot x^4$%, и далее $%x^{16}=x^8\cdot x^8$%. Всего получится 4 умножения вместо 15.

Для нахождения $%x^{15}$%, с учётом того, что $%15=1+2+4+8$%, надо перемножить между собой четыре выражения: $%x^{15}=x\cdot x^2\cdot x^4\cdot x^8$%. К этому моменту нам известны значения всех этих сомножителей, на что ранее было затрачено три умножения. К ним добавится ещё 3, итого будет 6.