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

Быстрое возведение в степень (бинарное) считает a^n за логарифмическое число умножений: на каждом шаге показатель делится на 2, основание возводится в квадрат, а при нечётном показателе результат домножается на текущее основание.

Сложность: время O(log n); память: O(1). Незаменимо в модульной арифметике и криптографии, где числа большие.

def power(a, n):
    result = 1
    while n > 0:
        if n & 1:
            result *= a
        a *= a
        n >>= 1
    return result

print(power(2, 10))  # 1024