Задача 73775

Темы:    [ Теория алгоритмов (прочее) ] [ Двоичная система счисления ] [ Показательные неравенства ] [ Логарифмические неравенства ]

Сложность: 6+ Классы: 9,10,11

Условие

Автор: Белага Э.Г.

По заданному ненулевому x значение x⁸ можно найти за три арифметических действия: x² = x · x, x⁴ = x² · x², x⁸ = x⁴ · x⁴, а x¹⁵ — за пять действий: первые три — те же самые, затем x⁸ · x⁸ = x¹⁶ и x¹⁶ : x = x¹⁶. Докажите, что

а) x¹⁶ можно найти за 12 действий (умножений и делений);

б) для любого натурального n возвести x в n-ю степень можно не более чем за 1 + 1,5 · log₂n действий.

Решение

Заметим сначала, что степени 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 умножений и одно деление.

Источники и прецеденты использования

журнал
Название	"Квант"
год
Год	1973
выпуск
Номер	12
Задача
Номер	М240