Бинарное возведение в степень

Бинарное (двоичное) возведение в степень — это приём, позволяющий возводить любое число в

$O(\log n)$

-ую степень за умножений (вместо умножений при обычном подходе).

Более того, описываемый здесь приём применим к любой ассоциативной операции, а не только к умножению чисел. Напомним, операция называется ассоциативной, если для любых

выполняется:

$(a \cdot b) \cdot c = a \cdot (b \cdot c)$

Наиболее очевидное обобщение — на остатки по некоторому модулю (очевидно, ассоциативность сохраняется). Следующим по "популярности" является обобщение на произведение матриц (его ассоциативность общеизвестна).

Алгоритм

Заметим, что для любого числа

и чётного числа выполнимо очевидное тождество (следующее из ассоциативности операции умножения):

$a^n = (a^{n/2})^2 = a^{n/2} \cdot a^{n/2}$

Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного

мы показали, как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.

Осталось понять, что делать, если степень

нечётна. Здесь мы поступаем очень просто: перейдём к степени , которая будет уже чётной:

$a^n = a^{n-1} \cdot a$

Итак, мы фактически нашли рекуррентную формулу: от степени

$2 \log n$

мы переходим, если она чётна, к , а иначе — к . Понятно, что всего будет не более переходов, прежде чем мы придём к

$O (\log n)$

(базе рекуррентной формулы). Таким образом, мы получили алгоритм, работающий за умножений.

Реализация

рекурсивная:

нерекурсивная простая:

нерекурсивная оптимизированная:

[ http://e-maxx.ru/algo/binary_pow ]

Page updated

Google Sites

Report abuse