Быстрое возведение в степень: как считать за O(log n)

Коротко

Для степени 10⁹ это разница между миллиардом умножений и тридцатью.

Идея

Наивный способ — умножить основание само на себя n раз:

result = 1
for _ in range(n):
    result *= base

Быстрый алгоритм опирается на два тождества:

a^n = (a^(n/2))²           если n чётное
a^n = a · a^(n-1)          если n нечётное

Каждый шаг уменьшает степень вдвое, поэтому шагов около log₂n.

Проследим на 3^13:

3^13 = 3 · 3^12
3^12 = (3^6)²
3^6  = (3^3)²
3^3  = 3 · 3^2
3^2  = (3^1)²
3^1  = 3

Шесть операций вместо тринадцати. При больших степенях разница становится колоссальной.

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

Прямая запись формул:

def power(base: int, exp: int) -> int:
    if exp == 0:
        return 1

    if exp % 2 == 0:
        half = power(base, exp // 2)
        return half * half          # важно: считаем ОДИН раз
    else:
        return base * power(base, exp - 1)


print(power(3, 13))   # 1594323
print(power(2, 10))   # 1024

Критичная деталь — переменная half. Если написать power(base, exp//2) * power(base, exp//2), рекурсия развернётся в два вызова вместо одного, и сложность станет O(n) вместо O(log n). Классическая ловушка.

Итеративная версия (двоичный алгоритм)

Более элегантный подход через двоичное представление степени.

Заметим: 13 в двоичном виде это 1101, то есть 8 + 4 + 1. Значит

3^13 = 3^8 · 3^4 · 3^1

Достаточно последовательно возводить основание в квадрат (получая a¹, a², a⁴, a⁸, …) и умножать в ответ те степени, у которых соответствующий бит установлен.

def power_iterative(base: int, exp: int) -> int:
    result = 1

    while exp > 0:
        if exp & 1:              # младший бит установлен
            result *= base
        base *= base             # переходим к следующей степени двойки
        exp >>= 1                # сдвигаем на бит вправо

    return result


print(power_iterative(3, 13))   # 1594323

Итеративная версия предпочтительнее: нет расхода стека и константа меньше.

Возведение по модулю

На практике чаще нужна не сама степень (она астрономически велика), а её остаток по модулю. Это основа криптографии и хеширования.

def power_mod(base: int, exp: int, mod: int) -> int:
    result = 1
    base %= mod                  # сразу уменьшаем

    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1

    return result


print(power_mod(2, 1000000007, 1000000007))   # 2
print(power_mod(3, 200, 1000000007))          # 605265149

Взятие остатка после каждого умножения обязательно. Без него промежуточные значения растут экспоненциально: в C++ или Java это переполнение, в Python — работа с гигантскими числами и катастрофическое замедление.

В Python это уже есть

Встроенная функция pow с тремя аргументами делает ровно это, причём на C:

pow(3, 13)              # 1594323
pow(2, 1000, 10**9 + 7) # быстрое возведение по модулю

Писать вручную стоит только для понимания или при переносе на другой язык. В боевом коде pow(a, b, m) быстрее любой ручной реализации.

Применение: обратный элемент по модулю

Деление по модулю напрямую не работает. Вместо него умножают на обратный элемент — число x, для которого a · x ≡ 1 (mod m).

По малой теореме Ферма, если m простое и a не делится на m:

a^(m-1) ≡ 1 (mod m)   ⟹   a^(m-2) ≡ a^(-1) (mod m)

MOD = 10 ** 9 + 7

def mod_inverse(a: int) -> int:
    return pow(a, MOD - 2, MOD)


# деление 10 на 3 по модулю
print(10 * mod_inverse(3) % MOD)   # 333333338
# проверка: 333333338 * 3 % MOD == 10

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

Применение: числа Фибоначчи за O(log n)

Красивое обобщение: быстрое возведение работает не только для чисел, но для любой ассоциативной операции. В частности, для умножения матриц.

Известное тождество:

| 1 1 |^n     | F(n+1)  F(n)   |
| 1 0 |    =  | F(n)    F(n-1) |

Значит n-е число Фибоначчи считается за O(log n) вместо O(n).

def matrix_multiply(a, b, mod=None):
    n = len(a)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                result[i][j] += a[i][k] * b[k][j]
            if mod:
                result[i][j] %= mod
    return result


def matrix_power(matrix, exp: int, mod=None):
    n = len(matrix)
    # единичная матрица
    result = [[int(i == j) for j in range(n)] for i in range(n)]

    while exp > 0:
        if exp & 1:
            result = matrix_multiply(result, matrix, mod)
        matrix = matrix_multiply(matrix, matrix, mod)
        exp >>= 1

    return result


def fibonacci(n: int, mod=10 ** 9 + 7) -> int:
    if n == 0:
        return 0
    return matrix_power([[1, 1], [1, 0]], n, mod)[0][1]


print(fibonacci(10))          # 55
print(fibonacci(1000000))     # мгновенно

Обратите внимание: структура matrix_power дословно повторяет power_iterative. Меняется только операция умножения и единичный элемент. Это и есть общность приёма.

Тем же способом решаются любые линейные рекуррентности — достаточно составить матрицу перехода.

Другие применения

Криптография. RSA и Диффи-Хеллман построены на возведении в степень по модулю с числами в сотни цифр. Без быстрого алгоритма они были бы невозможны.

Полиномиальное хеширование. Вычисление p^k mod M для скользящих хешей.

Комбинаторика по модулю. Сочетания через факториалы и обратные элементы.

Проверка простоты. Тест Миллера-Рабина многократно возводит в степень по модулю.

Частые ошибки

Двойной рекурсивный вызов. Разобрано выше — превращает логарифм в линию.

Забытый модуль внутри цикла. Числа растут неконтролируемо.

Отрицательная степень. Для целых чисел a^(-n) не определено; нужен обратный элемент по модулю или переход к вещественным числам.

Нулевая степень нуля. 0^0 математически спорно; в реализациях обычно возвращают 1. Проверьте, что требует условие задачи.

Что запомнить

• Быстрое возведение сводит O(n) умножений к O(log n).
• Чётная степень — квадрат половины, нечётная — умножение на основание.
• В рекурсивной версии обязательно сохраняйте результат в переменную.
• Итеративная версия читает биты степени и работает эффективнее.
• В Python используйте встроенный pow(a, b, m).
• Приём обобщается на матрицы, что даёт числа Фибоначчи и линейные рекуррентности за O(log n).

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→