Возведение в степень чисел

Рекурсивный подход

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

def pow(x, p):
    if p == 0:
        return 1
    t = pow(x * x, p // 2)
    if p % 2:
        t *= x
    return t

На каждом шаге рекурсии вы редуцируете задачу x**n и (x**2)**(n/2). Т.е. за один шаг вы вдвое понижаете степень.

Быстрое возведение в положительную целую степень

Эту идею можно реализовать и без рекурсии.

def pow(x, p):
    m = x
    t = 1
    while p:
        if p % 2:
            t *= m
        m *= m
        p //= 2
    return t

Мы получили логарифмическую сложность по времени, но уже константную сложно по памяти.

Быстрое возведение в любую целую степень

Любопытно, что небольшое дополнение к алгоритму позволяет расширить его возможности:

def pow(x, p):
    if p < 0:
        p = -p
        x = 1. / x
    m = x
    t = 1
    while p:
        if p % 2:
            t *= m
        m *= m
        p //= 2
    return t

Поиск чисел Фибоначчи

Напомню, то числа Фибоначчи — это последовательность, в котором два первых числа равны 0 и 1 (или 1 и 1), а каждое последующее равно сумме двух предыдущих.

Предлагаю принять такие обозначения:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)  при n >= 2

Числа Фибоначчи можно получать возведением в степень матрицы:

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

Справедливость этой формулы можно проверить разными способами. Можно внимательно присмотреться. Можно вспомнить/доказать, что F(n+m)=F(n-1)F(m)+F(n)F(m+1). Можно просто посмотреть, что будет при умножении матриц:

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

То есть, умножив матрицу из чисел Фибоначчи на матрицу с тремя единицами, мы сделали один шаг в последовательности Фибоначчи.

Быстрый поиск чисел Фибоначчи

def matrix_mul(a, b):
    return [[
        a[0][0] * b[0][0] + a[0][1] * b[1][0],
        a[0][0] * b[0][1] + a[0][1] * b[1][1]
    ], [
        a[1][0] * b[0][0] + a[1][1] * b[1][0],
        a[1][0] * b[0][1] + a[1][1] * b[1][1]
    ]]

def pow(p):
    m = [[1, 1], [1, 0]]
    t = [[1, 0], [0, 1]]
    while p:
        if p % 2:
            t = matrix_mul(t, m)
        m = matrix_mul(m, m)
        p //= 2
    return t

def fib(n):
    return pow(n)[1][0]

Это уже знакомы нам алгоритм возведения в степень, но не числа, а матрицы.

Быстрый поиск чисел Фибоначчи с помощью numpy

Используя библиотеки, решить эту задачу можно в одну строчку:

import numpy as np

def fib(n):
    return np.linalg.matrix_power(
        np.array([[1, 1], [1, 0]], dtype='O'),
        n
    )[1,0]

Единственно, что следует не забыть, это dtype='O', т.к. иначе, вы очень быстро упрётесь в ограничения разрядности. И, что самое печальное, numpy не предупредить вас об этом. Просто выдаст не правильный результат.