MathAlgorithmaka binary exponentiation, exponentiation by squaring, modpow, matrix exponentiation

Fast Exponentiation

Compute x^n in O(log n) multiplications by squaring x and multiplying it in wherever the binary expansion of n has a 1 bit.

▶ VisualizePattern: Divide and ConquerPractice (2)
Progress

Overview

Binary exponentiation computes x^n with O(log n) multiplications instead of n - 1. Write n in binary; x^13 = x^8 · x^4 · x^1 because 13 = 1101b. Square x repeatedly to get x, x², x⁴, x⁸ and multiply together the ones whose bit is set.

With every multiplication reduced modulo m, the same loop gives modular exponentiation x^n mod m without ever forming a huge number — the core of Modular Inverse by Fermat, Miller–Rabin primality, RSA, and hashing. Python's pow(x, n, m) does exactly this.

Since the loop only uses associativity, it works for any associative operation: matrix exponentiation raises the 2×2 matrix [[1,1],[1,0]] to the n-th power to get the n-th Fibonacci number in O(log n), and in general computes the n-th term of any linear recurrence of order k in O(k³ log n). It also handles string repetition, permutation powers, and function composition.

binary exponentiationmodpowmatrix powerFibonacciO(log n)

Intuition

A mental model before the formal terms.

To fold a paper 13 times you would not fold it 13 separate times from one sheet; you notice that after doubling three times you have 8 layers. Fast exponentiation is repeated doubling: keep a "current power" that squares each step (x → x² → x⁴ → x⁸), and only "cash in" the powers you actually need — those matching 1-bits of n. Every step halves n, so 13 needs 4 steps rather than 12 multiplications.

How it works

  1. Initialize result = 1, base = x mod m.
  2. While n > 0: if n is odd (n & 1), result = result · base mod m. Then base = base · base mod m and n = n >> 1.
  3. Return result. The loop runs ⌊log₂ n⌋ + 1 times, each with at most two multiplications.
  4. Matrix form: same loop, but result starts as the identity matrix and · is matrix multiplication. For Fibonacci, M^n = [[F(n+1), F(n)], [F(n), F(n-1)]].
  5. Negative exponents: x^-n = (x^-1)^n; for floats invert x, for modular arithmetic use the modular inverse.

Why it works

Invariant: at every iteration result · base^n equals the original x^n_original. Squaring base and halving n preserves it when n is even; when n is odd, moving one factor of base into result first makes n - 1 even. When n reaches 0, result holds the answer.

Modular reduction after every multiplication is valid because (a · b) mod m = ((a mod m) · (b mod m)) mod m — see Modular Arithmetic. Intermediates stay below m², which fits in 64 bits when m < 2^31.5 (e.g. 10^9 + 7).

Matrix version: [F(n+1), F(n)]^T = M · [F(n), F(n-1)]^T, so by induction [F(n+1), F(n)]^T = M^n · [F(1), F(0)]^T. Matrix multiplication is associative, so the same squaring scheme applies.

Recognition

How to tell a problem wants this.

  • "Compute x^n" with n up to 10^9 or 10^18, especially "modulo 10^9 + 7".
  • The n-th term of a linear recurrence for astronomically large n — Fibonacci with n = 10^18, tiling counts, number of walks of length n in a graph (adjacency matrix power).
  • Any associative operation that must be applied n times: apply a permutation k times, repeat a string transformation.
“merge k sorted” → Divide and Conquer“modulo 10^9 + 7” → Math & Number Theory

Interactive visualization

Play, step, change the input. ← → and space work too.

ee (binary)e & 1baseresult
131101·31
1/13Compute 3^13 mod 1000000007. Write the exponent in binary (1101): each 1-bit contributes base^(2^k), so we square the base once per bit instead of multiplying 13 times.
Current iterationBit is 1: multiply result by baseBit is 0: skip the multiplyFinished
PseudocodeLearn Fast Exponentiation →
1result = 1; base = base mod M
2while e > 0:
3  if e & 1: result = result · base mod M   # this bit is set
4  base = base · base mod M
5  e = e >> 1
6return result
Variables
base3
e13
result1
M1000000007
Complexity
best O(log n)
avg O(log n)
worst O(log n)
space O(1)
Speed

Pseudocode

1power(x, n, m):
2  result = 1, base = x mod m
3  while n > 0:
4    if n & 1: result = result * base mod m
5    base = base * base mod m
6    n = n >> 1
7  return result
8fib(n): return matpow([[1,1],[1,0]], n)[0][1]

Implementations

1# Exponentiation by squaring: x^n needs O(log n) multiplications, not n.
2# Read the exponent in binary; each 1-bit contributes the current square.
3 
4 
51 · Iterative binary exponentiation, modular to keep values bounded
6def pow_mod(base: int, exp: int, mod: int) -> int:
7    result = 1 % mod
8    base %= mod
9    while exp > 0:
10        if exp & 1:
11            result = result * base % mod
12        base = base * base % mod
13        exp >>= 1
14    return result
15 
16 
172 · The same recurrence written recursively: x^n = (x^(n/2))^2 * x^(n&1)
18def pow_mod_rec(base: int, exp: int, mod: int) -> int:
19    if exp == 0:
20        return 1 % mod
21    half = pow_mod_rec(base, exp // 2, mod)
22    sq = half * half % mod
23    return sq * (base % mod) % mod if exp & 1 else sq
24 
25 
263 · The trick is not about numbers: any associative operation works
27def mat_mul(a: list[list[int]], b: list[list[int]], mod: int) -> list[list[int]]:
28    n = len(a)
29    c = [[0] * n for _ in range(n)]
30    for i in range(n):
31        for k in range(n):
32            if a[i][k] == 0:
33                continue
34            aik = a[i][k]
35            row_b = b[k]
36            row_c = c[i]
37            for j in range(n):
38                row_c[j] = (row_c[j] + aik * row_b[j]) % mod
39    return c
40 
41 
424 · Matrix power gives the nth Fibonacci number in O(log n)
43def fibonacci(n: int, mod: int) -> int:
44    if n == 0:
45        return 0
46    result = [[1, 0], [0, 1]]  # identity
47    base = [[1, 1], [1, 0]]
48    e = n
49    while e > 0:
50        if e & 1:
51            result = mat_mul(result, base, mod)
52        base = mat_mul(base, base, mod)
53        e >>= 1
545 · result is base^n, and its top-right entry is F(n)
55    return result[0][1]
Walkthrough
  1. Python integers are arbitrary precision, so base * base % mod is exact with no cast, no __int128, and no BigInt — this is the shortest of the four versions for a reason.
  2. base %= mod needs no negative guard, because Python % always returns a result with the sign of the *divisor*, so a negative base normalises automatically.
  3. result = 1 % mod handles mod == 1 correctly.
  4. mat_mul hoists a[i][k], b[k] and c[i] into locals inside the loops, which removes repeated indexing from the innermost loop — the standard CPython optimisation.
  5. The ikj loop order (rather than ijk) makes the inner loop a straight scan over b[k] and c[i], which is both faster and what allows the a[i][k] == 0 skip.
Complexity (this implementation)
time O(log n) multiplications; O(k^3 log n) for a k x k matrix power · space O(1) iterative; O(log n) stack for the recursive form

The built-in pow(base, exp, mod) does exactly this in C and should always be preferred over the hand-written loop.

Language notes
  • The three-argument pow(base, exp, mod) is built in, implemented in C, and since Python 3.8 also handles a negative exponent as a modular inverse.
  • Python % returns a non-negative result for a positive modulus, unlike C++ and JavaScript — the negative-base normalisation is free.
  • Arbitrary-precision integers mean 2 ** 1000 is exact; the only cost is that each operation scales with the number of digits.
  • math.isqrt, math.comb and pow(..., -1, m) cover most of this topic's neighbours in the standard library.
Common mistakes in this language
  • Hand-writing the loop when pow(base, exp, mod) is available, C-implemented, and faster.
  • Writing base ** exp % mod, which computes the full unreduced power first — for a large exponent that exhausts memory rather than being merely slow.
  • Assuming % behaves like C++ and adding a redundant (harmless but confusing) negative-base guard.
Language differences that matter here
  • Wide arithmetic is the whole story: Python integers are unbounded, JS/TS must use BigInt (with a compile-time mixing check in TypeScript and a runtime TypeError in JavaScript), and C++ needs the non-standard __int128 extension for 64-bit modular multiplication.
  • Modulo sign: Python % follows the divisor and is always non-negative for a positive modulus; C++ and JS/TS follow the dividend, so both need the ((x % m) + m) % m normalisation.
  • Only Python has this built in — three-argument pow(base, exp, mod) — and it is faster than any hand-written loop.
  • The naive base ** exp % mod is a trap in every language, but it fails differently: an unbounded allocation in Python and JS/TS BigInt, and silent floating-point rounding with std::pow or Math.pow.

Complexity

Best
O(log n)
Average
O(log n)
Worst
O(log n)
Space
O(1)

Multiplications, each O(1) for fixed-width modular values. Matrix version is O(k^3 log n) for a k×k matrix. Recursive form uses O(log n) stack.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Powers with exponents beyond a few dozen, especially modular powers with n up to 10^18.
  • Modular inverse modulo a prime via a^(p-2) — see Modular Inverse.
  • Linear recurrences (Fibonacci, tilings, counting walks) at huge n via matrix powers; n-fold application of a permutation or function.
Avoid it when
  • Tiny exponents where a loop or x * x * x is clearer and just as fast.
  • Floating-point powers needing high precision — repeated squaring compounds rounding error; use exp(n · log x) or a library pow.
  • Recurrences where n is small enough for O(n) DP — the matrix approach adds constant factors and code.

Alternatives

Fibonacci NumbersTabulation (Bottom-Up DP)Modular Inverse

Common mistakes

  • Forgetting to reduce base modulo m before the loop, or reducing result but not base (or vice versa).
  • JavaScript: result * base with values near 10^9 exceeds 2^53 and loses precision — use BigInt (or split multiplication). Math.pow with a modulus is also wrong for large exponents.
  • Java/C++/Go: base * base overflows int64 when m > ~3·10^9; use 128-bit multiplication or a different approach.
  • Negative n handled as an infinite loop in the integer version; handle the sign first.
  • Matrix exponentiation off-by-one: M^n[0][1] = F(n), and n = 0 must be special-cased if the identity matrix is not used.

Interview patterns

  • Pow(x, n) with negative exponents and n = INT_MIN edge case (negate as a long first).
  • Fibonacci / climbing stairs / tiling for n up to 10^18 mod 10^9 + 7.
  • Count the number of length-n walks between two vertices: A^n where A is the adjacency matrix.
  • Super Pow: a^b mod 1337 where b is given as a digit array — process digit by digit with result = result^10 · a^digit.
Interview questions on this
Mock interviews

Example problems

Climbing StairseasyPow(x, n)medium