Бинарное возведение в степень - Алгоритмика
Бинарное возведение в степень

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

авторы Сергей Слотин Максим Иванов

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

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

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

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

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

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

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

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

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

$$ a^n = f(a, n) = \begin{cases} 1, && n = 0 \\ f(a, \frac{n}{2})^2, && 2 \mid n \\ f(a, n - 1) \cdot a, && 2 \nmid n \end{cases} $$

Так как каждые два перехода $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$, то

$$ a^{42} = a^{32+8+2} = a^{32} \cdot a^8 \cdot a^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$ выполняется:

$$ (a \circ b) \circ c = a \circ (b \circ 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;
}

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

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

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

$$ S = 1 + a + a^2 + \ldots a^{n-1} $$ В простом случае это сумма геометрической прогрессии, и алгебраически она равна $\frac{1-a^n}{1-a}$, так что можно просто посчитать $a^n$ бинарным возведением в степень, а затем провести деление $(1-a^n)$ на $(1-a)$. Однако в общем случае так сделать нельзя — например, хотя бы потому, что не по всем модулям будет существовать обратное. Поэтому бинарное возведение в степень для таких формул нужно несколько модифицировать: $$ \begin{aligned} f(a, n) &= 1 + a + a^2 + \ldots a^{n-1} \\ &= (1 + a + \ldots + a^{n/2}) + a^{n/2} \cdot (1 + a + \ldots a^{n/2}) \\ &= (1 + a^{n/2}) \cdot f(a, n) \end{aligned} $$ В самом алгоритме нужно помимо степеней $a$ поддерживать ещё и суммы всех степеней от $1$ до $a^k$.