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

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

O(\log n)
n
n

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

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

a, b, c

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

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

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

Алгоритм

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

a
n

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

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

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

n

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

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

n-1
n

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

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

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

n/2
n-1
2 \log n
n

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

O (\log n)
n = 0

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

Реализация

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

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

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