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

Продолжим рассматривать эффективные методы вычислений.

Попробуем научиться быстро возводить число x в целую неотрицательную степень p. Кажется, нет ничего проще, чем вычислить xp: надо сделать цикл из n шагов:

def power_naive(x, p):
    result = 1
    for _ in range(p):
        result *= x
    return result

Сложность — O(n) умножений.

Применим метод «разделяй и властвуй» к нашей задаче. Это поможет выделить подзадачи.

Определим возведение в степень.

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

Например, чтобы вычислить 2^17, мы выполняем следующие шаги:

217 = 2 ∗ 216

216 = (2 ∗ 2)8 = 48

48 = (4 ∗ 4)4 = 164

164 = (16 ∗ 16)2 = 2562

2562 = (256 ∗ 256)1 = 655361

655361 = 65536

Получается, мы сделали всего 5 умножений, а не 17, потому что воспользовались наивным алгоритмом.

А вот и наш красивый код:

def power_fast(x, p):
    if p == 0:
        return 1
    if p == 1:
        return x
    if p % 2 == 0:
        return power_fast(x * x, p // 2)
    else:
        return x * power_fast(x, p - 1)

Сложность этого алгоритма O(log2⁡n).