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

Пусть у нас есть какая-то ассоциативная бинарная операция $\circ$ в алгебре $\AAA$ . Мы хотим научиться быстро считать степень элемента $a$ носителя алгебры $\AAA$ по этой операции, то есть значение

a^n = \underbrace{a \circ a \circ \dotsb \circ a \circ a}_{n ~\text{раз}}

В псевдокоде я заменю операцию $\circ$ на умножение, но это просто для удобства написания. В формулах я буду использовать оригинальное обозначение, дабы подчеркнуть универсальность.

Можно применить свойство ассоциативности для сведения задачи возведения в степень $n$ к вдвое меньшей задаче, используя простое свойство

a^n = \cases{a^{n/2} \circ a^n & n~\text{чётное} \\ a \circ a^{n-1} & n~\text{нечётное}}

Из этого простого свойства можно сразу вывести простой рекурсивный алгоритм

function fast_pow(a, int n):
    if n % 2 == 0:
        return fast_pow(a, n/2) ** 2
    else:
        return a * fast_pow(a, n-1)

У рекурсии есть оверхед, от которого хотелось бы избавиться.

Давайте посмотрим на двоичное представление $n$

n = (n_k \, n_{k-1} \, \dotsm \, n_2 \, n_1 \, n_0)_2 = n_k \cdot 2^k + n_{k-1} \cdot 2^{k-1} + \dotsb + n_2 \cdot 4 + n_1 \cdot 2 + n_0

Тогда нашу степень можно переписать как

n = ((( \dotsm ((n_k \cdot 2 + n_{k-1}) \cdot 2 + n_{k-2}) \cdot 2 + \dotsm) \cdot 2 + n_2) \cdot 2 + n_1) \cdot 2 + n_0

Ну и здесь сразу видно, как производить вычисления

function fast_pow(a, int n):
    int result = 1
    while n > 0:
        if n % 2 == 1:
            result *= a
        a *= a
        n /= 2;
    return result

Важное замечание: $1$ в этом алгоритме — нейтральный элемент по операции $\circ$ .

Оценим количество умножений, требуемых алгоритмом (не важно каким, они одинаковые). Пусть для возведения числа $a$ в степень $n$ требуется $M(n)$ умножений. Тогда, исходя из нашего алгоритма, справедлива формула

M(n) = M\left( \left\lfloor \frac{n}{2} \right\rfloor \right) + 1 + (n \bmod 2)

Решение этого уравнения

M(n) = \lfloor \log_2 n \rfloor + \nu(n) - 1

где $\nu(n)$ — количество единиц в числе $n$

Предподсчёт

Пусть у нас есть фиксированный объект $a$ . К нам поступает $q$ запросов возведения $a$ в степень $m_i$ ( $i$ - номер запроса).

Только что мы научились решать эту задачу за $\sum\limits_{i=1}^q \bigl( \lfloor \log_2 m_i \rfloor + \nu(m_i) \bigr)$ умножений, что в итоге выливается в временную сложность $O(q \cdot \log \max\limits m) \cdot \time(\text{одно умножение})$

Аддитивные цепочки и оптимальный алгоритм