Заметим сначала, что степени x с показателями2,4,8, ... ,2^k можно вычислить за k умножений, именно: x²=x · x , x⁴=x² · x² , ... , x2^k=x2^k-1 · x2^k-1. Отсюда следует, что xⁿ= x2^{log 2 n} нельзя найти быстрее чем за l=[log 2 n]операций (через[z]обозначена целая часть действительного числа z , т.е. такое целое число m , что m z<m+1).

а) Так как 2⁹=512<1000<1024=210, т.е. [log _{_}2 1000]=9, то x1000 нельзя вычислить быстрее чем за 9 действий. С другой стороны, x1000= x1024:(x16 · x⁸), на что потребуется 11 умножений и 1 деление. Можно доказать, что этот способ вычисления самый экономный.

Замечание. В "Кванте" #11 за 1973 год была опубликована задача из книжки Е.А.Морозовой и И.С.Петракова, Международные математические олимпиады:

Дан ящик сахарного песка, чашечные весы и гирька в 1г. Как возможно быстрее отвесить покупателю 1кг сахару? (Указать схему уравновешиваний.)

Несмотря на различие в формулировках, в действительности задачи M240а) и только что приведенная в точности совпадают, и теперь вы уже можете указать ответ и на этот вопрос.

б) Опишем теперь способ вычисления xⁿ . Он основывается на двоичном представлении n ₂ числа n .

Представим n в виде суммы

n=ε_l · 2^l+ε_l-1 · 2^l-1+...+ ε₁ · 2+ε₀,

где ε_j – либо0, либо1,0 j l-1, а ε_l=1. Тогда двоичное представление n имеет вид:

n ₂=ε_l ε_l-1 ... ε₁ ε₀ (*)

Обозначим через E(n) число единиц среди цифр ε_j :

1 ε_l+ε_l-1+...+ε₁+ε₀= E(n) l+1,

а через H(n)– число нулей, так что H(n)=l+1-E(n). Для нахождения xⁿ вычисляем сначала многочлены x² , x⁴ , ... , x2^l (за l умножений). Дальнейшие вычисления зависят от величины E(n).

(1) Если 1 E(n) , то перемножим те многочлены x2^j , для которых ε_j=1 (для этого нам потребуется E(n)-1 умножений); ввиду равенства(*), результат ранен xⁿ , общее же число умножении равно l+E(n)-1.

Но

l+E(n)-1 l+< log _{_}2 n+1.

(2) Если <E(n) l+1, то

H(n) .

Рассмотрим число =2^l+1-n . Очевидно, что n ₂+ ₂=10 ... 0( l+1нуль) и что поэтому E () H(n)+1. Как и в случае (1), вычислим многочлен x за l+E()-1умножений. Затем вычислим многочлен x2^l+1(так как многочлен x2^l уже найден, то на это потребуется еще одно умножение) и, наконец, многочлен xⁿ=x2^l+1: x (одно деление). Итак, в этом случае потребовалось l+ E ()умножений и одно деление, т.е. всего l+E () +1действий, где

l+E ()+1 l+H(n)+2 l+1 log _{_}2 n+1.

Замечание. Многочлен x1000 был вычислен нами способом(2). Однако существуют многочлены, для которых ни способ(1), ни способ(2) не являются наилучшими. Например, многочлен x170 может быть вычислен за 9 умножений (найдите такой способ сами!), хотя 170 ₂=10,101,010, так что E(170)=H(170)=4, [log _{_}2 170]=7; при способе(1) нужно 10 умножений, а при способе(2)– 11 умножений и одно деление.

Ответ задачи отсутствует