Fast Exponentiation (Binary Exponentiation)

Fast exponentiation (binary exponentiation, exponentiation by squaring) computes a^n with O(log n) multiplications instead of n - 1. It is the standard answer to "implement pow(x, n)", the core of modular exponentiation, and it works for anything you can multiply associatively: integers mod m, matrices, permutations.

Intuition

Write the exponent in binary. For example 13 = 1101 in binary = 8 + 4 + 1, so a^13 = a^8 * a^4 * a^1. The powers a, a^2, a^4, a^8, ... are obtained by repeated squaring, one squaring per bit. Walk through the bits of n from the lowest: square the base every step, and multiply it into the result whenever the current bit is 1.

The recursive view says the same thing: a^n = (a^(n/2))^2 when n is even and a * (a^((n-1)/2))^2 when odd. Either way the number of multiplications is about 2 * log2(n).

Nothing in the argument uses commutativity or numbers specifically; it only needs an associative multiplication with an identity element. That is why the same loop computes matrix powers (linear recurrences in O(log n)), applies a permutation k times, or composes a function with itself.

When to use it in interviews / OAs

• "Implement pow(x, n)", possibly with negative n.
• Any answer of the form a^b mod m with b up to 10^18 (counting problems with independent choices per position, modular inverses via Fermat).
• The exponent is given as a huge number or a digit array.
• Applying the same transformation k times with k up to 10^9 or more.

Template

def fast_pow(base: int, exp: int) -> int:
    result = 1
    while exp > 0:
        if exp & 1:  # this bit of exp is set: multiply the current power in
            result *= base
        base *= base  # base^(2^i) becomes base^(2^(i+1))
        exp >>= 1
    return result


def mod_pow(base: int, exp: int, mod: int) -> int:
    result = 1 % mod  # also correct when mod == 1
    base %= mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

In Python, the built-in pow(base, exp, mod) does exactly this (and pow(a, -1, m) returns a modular inverse since 3.8), but interviewers usually want to see the loop. The recursive form is a nice alternative to explain:

def pow_recursive(base: int, exp: int, mod: int) -> int:
    if exp == 0:
        return 1 % mod
    half = pow_recursive(base, exp // 2, mod)
    half = half * half % mod
    return half * base % mod if exp & 1 else half

Floating-point pow(x, n) with negative n: invert the base and negate the exponent.

def my_pow(x: float, n: int) -> float:
    if n < 0:
        x, n = 1 / x, -n  # in C++/Java negate in 64 bits: -(-2^31) overflows an int
    result = 1.0
    while n:
        if n & 1:
            result *= x
        x *= x
        n >>= 1
    return result

Beyond numbers: any associative operation

A generic version takes the multiplication and identity as parameters. Raising a permutation to the k-th power answers "where does each element end up after shuffling k times":

def power(x, n: int, mul, identity):
    result = identity
    while n:
        if n & 1:
            result = mul(result, x)
        x = mul(x, x)
        n >>= 1
    return result


def permutation_power(perm: list[int], k: int) -> list[int]:
    # result[i] = perm applied k times to i
    def compose(p: list[int], q: list[int]) -> list[int]:
        return [p[j] for j in q]  # first q, then p

    return power(perm, k, compose, list(range(len(perm))))

Each composition is O(n), so k applications cost O(n log k) instead of O(n k). Matrix exponentiation is the same function with matrix multiplication plugged in.

Huge exponents given as digits

To compute a^b mod m where b is a digit array, process digits left to right: appending a digit d to the exponent turns a^e into (a^e)^10 * a^d.

def super_pow(a: int, digits: list[int], mod: int = 1337) -> int:
    result = 1
    for d in digits:
        result = mod_pow(result, 10, mod) * mod_pow(a, d, mod) % mod
    return result

When gcd(a, m) = 1, Euler's theorem also lets you reduce the exponent modulo phi(m) first; for a prime modulus that is m - 1.

Complexity

O(log n) multiplications. With a modulus that fits in a machine word each multiplication is O(1); with matrices of size k it is O(k^3) per multiplication, so O(k^3 log n) in total; for permutations of length n it is O(n log k).

Common pitfalls

• Negative exponents: invert the base first; in C++/Java store n in a 64-bit variable before negating, because -INT_MIN overflows.
• Overflow in C++/Java: result * base must fit in 64 bits, so reduce after every multiplication and keep the modulus below about 3 * 10^9. For larger moduli use __int128 or "multiply by doubling" (the same loop with addition instead of multiplication).
• Forgetting to reduce the base: base %= mod first, especially when the base can be negative or larger than the modulus.
• mod = 1: everything is 0; starting with result = 1 would wrongly return 1 when exp == 0.
• 0^0: by convention the loop returns 1; decide whether the problem agrees.
• Wasted last squaring with big integers: without a modulus, the final base *= base can be huge; for very large exponents break out before squaring when exp == 1.

Interview variations

• pow(x, n) with negative exponents and doubles.
• Super pow: exponent given as a digit array.
• Count good numbers: choices per position are independent, so the count is 5^(even positions) * 4^(odd positions) mod 10^9+7.
• Modular inverse for a prime modulus: a^(p-2) mod p (Fermat's little theorem).
• Fibonacci or any linear recurrence in O(log n): fast (binary) exponentiation of a small matrix.
• Repeat a permutation or a state transition k times: generic power over composition.