Fast ExponentiationFast exponentiation

01Why it exists

Reach for it when you see:x to the n-th power, a huge n (10⁹, 10¹⁸), an answer taken modulo something, RSA and modular exponentiation, term n of a linear recurrence, a matrix to the n-th power, applying the same operation n times, needing O(log n) multiplications.

02The core idea

The direct way to compute xⁿ is n − 1 multiplications. Fast exponentiation uses divide and conquer to halve the exponent: xⁿ = (x^⌊n/2⌋)², with one extra x when n is odd. Compute the half, square it once, and you have the whole thing. The recurrence is T(n) = T(n/2) + O(1), which lands in case 2 of the Master Theorem with a = 1, b = 2, d = 0 — O(log n) multiplications. The most common mistake is calling power(x, n/2) twice and multiplying the results: the recurrence becomes T(n) = 2T(n/2) + O(1) and you are back at O(n). Computing the half exactly once is the whole point.

The iterative version is the same idea seen through binary. Write n as Σ bᵢ·2ⁱ and you get xⁿ = ∏ x^(2ⁱ), keeping only the terms where bᵢ = 1. Scan from the low bit to the high bit maintaining two invariants: before handling bit i, base = x^(2ⁱ) and result = x^(the low i bits of n). If bit i is 1, multiply base into result; then square base into x^(2ⁱ⁺¹) and shift n right by one. Once every bit is handled, "the low bits" means all of n, and result is exactly xⁿ. This form needs no recursion and O(1) extra space.

Complexity: n has ⌊log₂ n⌋ + 1 bits and each bit costs at most one squaring plus one multiplication, so no more than 2 log₂ n multiplications in total — make the exponent ten times larger and you add three or four bits. Note that this O(log n) counts multiplications: under a modulus each multiplication is O(1), but on unbounded integers with no modulus the numbers keep growing and each multiplication gets more expensive on its own. For space, the iterative version is O(1) while the recursive one needs an O(log n) call stack. Fast exponentiation relies only on associativity and the existence of a "1" (an identity element), so it is not limited to numbers: the "1" for matrices is the identity matrix, one k×k matrix multiplication is O(k³), and the total is O(k³ log n) — this is how matrix exponentiation gets term n of a linear recurrence. Permutations, affine transforms and anything else that composes can be doubled up the same way.

Common traps: overflow — reduce after every multiplication, and make sure the product of two values below mod fits in your type; a 64-bit integer is enough for mod = 10⁹+7, but a mod near 10¹⁸ needs 128 bits or a special multiplication routine. Negative exponents (LeetCode 50) call for taking the reciprocal first, and negating a 32-bit INT_MIN overflows, so widen to 64 bits before you do. And x⁰ = 1 including when x = 0, while mod = 1 should give 0, which is why the initial value is written 1 % mod. As for the neighbouring lessons: the binary search in the Master Theorem lesson has the same recurrence as this one, and Modular Arithmetic in the maths section uses fast exponentiation for modular inverses — Fermat's a^(p−2) mod p.

03The algorithm

1. 1Initialise result = 1 % mod and base = x % mod.
2. 2While n > 0: if n & 1 is 1, set result = result × base % mod.
3. 3Set base = base × base % mod and n >>= 1, then go back to the previous step. Each round handles one bit of n.
4. 4When n reaches 0, result is the answer. The recursive form instead computes half = power(x, n // 2) and returns half² or half² × x — the half is computed exactly once.
5. 5To switch to matrices, or any other associative operation, replace 1 with the identity element and multiplication with that operation. Nothing else changes.

04Interactive demo

The base is fixed at 3 and you can switch the exponent between 13, 25 and 100. The exponent's binary form is on top with the low bit on the right, and the row above it labels each bit's weight. Bits are handled one at a time from low to high: blue is the bit being processed, and a processed bit turns green if it was a 1. The table records base (that is, 3 raised to 2ⁱ) and result at each bit, with every multiplication taken modulo 10⁹+7. The two bars on the right compare multiplication counts: exponent 13 takes 6, 25 takes 7, and 100 takes only 9, against 12, 24 and 99 for multiplying one factor at a time.

05Code

Python has the recursive version, the iterative modular power, and the same loop applied to 2×2 matrices to reach term 10¹⁸ of the Fibonacci sequence. C++ has the modular power, the LeetCode 50 version that handles floating point and negative exponents (watch INT_MIN), and matrix exponentiation. All three loops look identical; the only difference is what "1" and "multiply" mean.

# Recursive: x^n = (x^(n//2))², with one extra x when n is odd
def power_rec(x, n):
    if n == 0:
        return 1
    half = power_rec(x, n // 2)          # recurse once only; two calls would degrade this to O(n)
    return half * half * (x if n % 2 else 1)


# Iterative: scan n's bits from low to high, squaring base each round
def power_mod(x, n, mod):
    result, base = 1 % mod, x % mod
    while n > 0:
        if n & 1:                        # this bit is 1: multiply x^(2^i) into the answer
            result = result * base % mod
        base = base * base % mod         # x^(2^i) → x^(2^(i+1))
        n >>= 1
    return result


# The same routine on matrices: [[1, 1], [1, 0]]^n = [[F(n+1), F(n)], [F(n), F(n-1)]]
def mat_mul(A, B, mod):
    return [[(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % mod, (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % mod],
            [(A[1][0] * B[0][0] + A[1][1] * B[1][0]) % mod, (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % mod]]


def fib_mod(n, mod):
    result, base = [[1, 0], [0, 1]], [[1, 1], [1, 0]]   # the identity matrix is the "1" of matrices
    while n > 0:
        if n & 1:
            result = mat_mul(result, base, mod)
        base = mat_mul(base, base, mod)
        n >>= 1
    return result[0][1]                  # the top-right entry is F(n)


if __name__ == "__main__":
    print(power_rec(3, 13), power_rec(2, 10))      # 1594323 1024
    MOD = 10**9 + 7
    print(power_mod(3, 25, MOD), pow(3, 25, MOD))  # 288603514 288603514 (the built-in three-argument pow is fast exponentiation)
    print(fib_mod(10, MOD), fib_mod(10**18, MOD))  # 55 209783453 (term 10¹⁸ takes only about 60 rounds)

06Practice

• LeetCode 509Fibonacci Number (get to O(log n) with matrix exponentiation)Easy
• LeetCode 50Pow(x, n) (negative exponents and INT_MIN)Medium
• LeetCode 1922Count Good Numbers (n up to 10¹⁵; the answer is two modular powers multiplied)Medium
• LeetCode 372Super Pow (the exponent arrives as a very long array of decimal digits)Medium
• LeetCode 1969Minimum Non-Zero Product of the Array Elements (derive the formula first, then use a modular power)Medium