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

Бинарное возведение в степень — приём, позволяющий возводить любое число в $n$-ую степень за $O(\log n)$ умножений (вместо $n$ умножений при обычном подходе).

#Основная идея

Заметим, что для любого числа $a$ и чётного числа $n$ выполняется тождество:

Получается, что для любого чётного $n$ мы можем свести задачу к вдвое меньшей ($n’ = \frac{n}{2}$), потратив всего одну операцию умножения.

Если же $n$ нечётно, то верно следующее:

Получается, для нечетных $n$ мы можем сделать сведение к задаче размера $(n-1)$, которая уже будет чётной.

Мы фактически нашли рекуррентную формулу для подсчета $a^n$:

Так как каждые два перехода $n$ гарантированно уменьшается хотя бы в два раза, всего будет не более $2 \cdot \log_2 n$ переходов, прежде чем мы придём к $n = 0$. Каждый переход требует ровно одно умножение, и таким образом, мы получили алгоритм, работающий за $O(\log n)$ умножений.

#Реализация

Сразу напрашивается рекурсивная реализация этого алгоритма:

int binpow(int a, int n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1)
        return binpow(a, n - 1) * a;
    else {
        int b = binpow(a, n / 2);
        return b * b;
    }
}

Эта реализация рекурсивная, что работает долго. Попробуем «развернуть» рекурсию и получить итеративную.

Рассмотрим двоичное представление числа $n$. Результат $a^n$ можно представить как произведение $a$ в степенях каких-то степеней двоек. Например, если $n = 42 = 32 + 8 + 2$, то

Чтобы посчитать это произведение итеративно, пройдемся по всем битам числа $n$, поддерживая две переменные: непосредственно результат и текущее значение $a^{2^k}$, где $k$ это номер текущей итерации. На каждом шаге будем домножать $a^{2^k}$ на текущий результат, если $k$-тый бит числа $n$ единичный, и в любом случае возводить её в квадрат, получая $a^{2^k \cdot 2} = a^{2^{k+1}}$ для следующей итерации.

int binpow(int a, int n) {
    int res = 1;
    while (n != 0) {
        if (n & 1)
            res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}

Стоит отметить, что во многих языках программирования бинарное возведение в степень уже реализовано. Но не в C++: функция pow из стандартной библиотеки реализована только для действительных чисел и использует приближенные методы, и поэтому не дает точных результатов для целочисленных аргументов.

#Обобщения

Бинарное возведение в степень применимо не только к умножению чисел, а вообще к любым ассоциативным операциям — таким, для любых $a$, $b$ и $c$ выполняется:

Наиболее очевидное обобщение — на остатки по модулю:

const int mod = 1e9 + 7;

long long binpow(long long a, int n) {
    long long  res = 1;
    while (n != 0) {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

Вторым самым «популярным» обобщением является произведение матриц, про которое мы подробнее поговорим в следующей статье.

#Геометрические прогрессии

Возводить какие-то объекты в степень часто нужно в контексте комбинаторики, и помимо этого, иногда требуется считать суммы подобного вида: