Fast Exponentiation

Fast Exponentiation (Binary Exponentiation)

Computing a^n sounds trivial: just multiply a by itself n times. But when n is a billion, that naive loop performs a billion multiplications. Fast exponentiation, also called binary exponentiation or exponentiation by squaring, reduces that to roughly 30 multiplications by exploiting a simple mathematical identity.

Why Naive Multiplication Fails

The straightforward approach runs in $O(n)$ time. For competitive programming problems and cryptographic computations, exponents routinely reach $10^9$ or larger. An $O(n)$ loop becomes completely infeasible. The fix comes from noticing that you can reuse work.

The Squaring Trick

The core insight is splitting the problem in half at each step:

• If n is even: a^n = (a^(n/2))^2
• If n is odd: a^n = a * a^(n-1) (which reduces to the even case)

This gives a recurrence that halves n on every step, yielding $O(\log n)$ total multiplications.

Thinking in Binary

Another way to see why this works: write n in binary. For example, 13 in binary is 1101, meaning 13 = 8 + 4 + 1. Therefore:

a^13 = a^8 * a^4 * a^1

The iterative algorithm scans the bits of n from least significant to most significant. Whenever a bit is 1, it multiplies the running result by the current power of a. After each bit, it squares a to advance to the next power.

Walked Example: Computing $3^{13}$

Start with result = 1, a = 3, n = 13 (binary: 1101).

• Bit 0 is 1 → result = 1 * 3 = 3. Square: a = 9. n = 6.
• Bit 0 is 0 → skip. Square: a = 81. n = 3.
• Bit 0 is 1 → result = 3 * 81 = 243. Square: a = 6561. n = 1.
• Bit 0 is 1 → result = 243 * 6561 = 1594323. n = 0. Done.

Check: $3^{13}$ = 1594323. Four multiplications instead of twelve.

The Iterative Implementation

def power(a, n, mod=None):
    result = 1
    if mod:
        a = a % mod
    while n > 0:
        if n % 2 == 1:                          # current bit is set
            result = result * a % mod if mod else result * a
        n //= 2                                 # shift to next bit
        a = a * a % mod if mod else a * a       # square for next bit position
    return result

The mod parameter is critical for most competitive programming problems. Without it, intermediate values grow exponentially and overflow in languages with fixed-width integers (Python handles big integers natively, but other languages do not). Always apply the modulus after every multiplication, not just at the end.

Python's built-in pow(a, n, mod) does exactly this and is implemented in C, so it is faster than a hand-written version. Reach for it first; only write your own when you need to adapt the structure (e.g., for matrix exponentiation).

Matrix Exponentiation: Fibonacci in $O(\log n)$

The squaring trick generalizes to any associative operation, including matrix multiplication. The Fibonacci recurrence F(n) = F(n-1) + F(n-2) can be expressed as a matrix equation:

| F(n+1) |   | 1 1 |^n   | 1 |
| F(n)   | = | 1 0 |   * | 0 |

Raising the $2 \times 2$ transition matrix to the nth power via fast exponentiation computes F(n) in $O(\log n)$ time, a massive improvement over $O(n)$ iteration when $n$ can reach $10^{18}$.

def mat_mul(A, B, mod):
    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            if A[i][k] == 0:
                continue
            for j in range(n):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod
    return C

def mat_pow(M, n, mod):
    size = len(M)
    result = [[1 if i == j else 0 for j in range(size)] for i in range(size)]  # identity
    while n > 0:
        if n % 2 == 1:
            result = mat_mul(result, M, mod)
        n //= 2
        M = mat_mul(M, M, mod)
    return result

def fibonacci(n, mod=10**9 + 7):
    if n <= 1:
        return n
    M = [[1, 1], [1, 0]]
    return mat_pow(M, n, mod)[0][1]

This pattern handles any linear recurrence of fixed order: compute the transition matrix once, then exponentiate it.

Modular Inverse via Fermat's Little Theorem

When working modulo a prime p, Fermat's little theorem states that a^(p-1) ≡ 1 (mod p) for any a not divisible by p. Rearranging, the modular inverse of a is:

a^(-1) mod p = pow(a, p - 2, p)

This is the standard way to compute modular inverses needed for division in modular arithmetic, for example when computing combinations C(n, k) mod p:

MOD = 10**9 + 7

def mod_inv(a, p=MOD):
    return pow(a, p - 2, p)

def comb_mod(n, k, p=MOD):
    if k > n:
        return 0
    num = 1
    den = 1
    for i in range(k):
        num = num * (n - i) % p
        den = den * (i + 1) % p
    return num * mod_inv(den, p) % p

Super Pow: Exponent Given as an Array

LeetCode 372. Super Pow asks you to compute a^b mod 1337 where b is given as an array of digits, potentially representing a number far too large to store in a single integer.

The trick is to process b digit by digit. If b = [1, 5, 6, 4], then a^1564 = ((a^1)^10 * a^5)^10 * a^6)^10 * a^4. At each step, raise the running result to the 10th power and multiply by a^(current digit).

def superPow(a, b):
    MOD = 1337
    result = 1
    for digit in b:
        result = pow(result, 10, MOD) * pow(a, digit, MOD) % MOD
    return result

Each iteration does two modular exponentiations with small exponents (at most 10), so each step is $O(\log 10) = O(1)$ and the whole computation is $O(d)$ where $d$ is the number of digits in b.

Count Good Numbers

Consider LeetCode 1922. Count Good Numbers: a digit string of length n is "good" if even-indexed positions (0, 2, 4, ...) contain an even digit (5 choices: 0, 2, 4, 6, 8) and odd-indexed positions contain a prime digit (4 choices: 2, 3, 5, 7). Count the total good strings of length n, modulo $10^9 + 7$.

The even positions number ceil(n/2) and the odd positions number floor(n/2). The answer is simply $5^{\lceil n/2 \rceil} \times 4^{\lfloor n/2 \rfloor} \mod (10^9 + 7)$, computed with fast exponentiation.

def countGoodNumbers(n):
    MOD = 10**9 + 7
    evens = (n + 1) // 2   # ceil(n/2)
    odds = n // 2           # floor(n/2)
    return pow(5, evens, MOD) * pow(4, odds, MOD) % MOD

Without fast exponentiation, computing $5^{5 \times 10^{14}}$ would be completely infeasible. With it, the computation takes about 50 multiplications.

Modular Combinatorics with Precomputed Factorials

For problems that require many $\binom{n}{k} \mod p$ queries (such as counting paths in a grid or coefficients in polynomial expansions), precomputing factorials and their inverses up front is more efficient than computing each combination from scratch. The inverse of k! is computed via fast exponentiation using Fermat's little theorem: inv(x) = x^(p-2) mod p.

MOD = 10**9 + 7

def precompute(n):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % MOD
    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], MOD - 2, MOD)
    for i in range(n - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
    return fact, inv_fact

def nCr(n, r, fact, inv_fact):
    if r < 0 or r > n:
        return 0
    return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD

The precomputation is $O(n)$ time (one exponentiation for the last inverse factorial, then fill the rest by multiplying backwards). After that, each combination query is $O(1)$. This is the standard technique for combinatorics in competitive programming.

Pow(x, n)

LeetCode 50. Pow(x, n) is the canonical interview problem for binary exponentiation. Given a floating-point base x and integer exponent n (which can be negative), compute x^n. Handle negative exponents by negating n and inverting x.

def myPow(x, n):
    if n < 0:
        x = 1 / x
        n = -n
    result = 1.0
    while n > 0:
        if n & 1:
            result *= x
        x *= x
        n >>= 1
    return result

The pitfall: with naive iteration, computing x^(-2^31) is two billion multiplications. With binary exponentiation, 31.

When to Reach for It

Any time you compute a^n with large n, especially under a modulus, reach for fast exponentiation, or Python's built-in pow(a, n, mod). The technique also applies whenever the underlying operation is associative: matrix powers for linear recurrences, transition tables for long-range graph reachability (LeetCode 1976. Number of Ways to Arrive at Destination-style problems), or polynomial evaluation modulo a prime. The signal is "raise to a large power" or "iterate a linear update many times."

Complexity

Fast exponentiation performs $O(\log n)$ multiplications. For scalar integers, each multiplication is $O(1)$, making the overall time complexity $O(\log n)$ with $O(1)$ space when written iteratively. For matrix exponentiation with $k \times k$ matrices, each matrix multiplication costs $O(k^3)$, so the overall complexity is $O(k^3 \log n)$. For Fibonacci with $k = 2$, this is $O(\log n)$ with a small constant.

Recognizing this pattern

You're probably looking at fast exponentiation when:

• You need to compute x^n or x^n mod m with n up to 10^18 (linear iteration would TLE).
• The recurrence is linear and n is huge, with Fibonacci-style transitions where a matrix power gives the answer.
• The problem asks for a count modulo a prime and involves repeated multiplications of the same factor.
• The underlying operation is associative (multiplication, matrix mult, composition of transformations) and you're applying it many times.

Common templates:

• Scalar binary exponentiation: square-and-multiply for x^n (with optional modulus). Example: Pow(x, n).
• Modular exponentiation: same loop, every product reduced mod m. Example: Super Pow.
• Matrix exponentiation: raise a transition matrix to the nth power for linear recurrences. Example: Fibonacci Number.
• Transition-table power: apply the same step many times in a state machine or path-count problem. Example: Knight Dialer.