Skip to content

Binary Exponentiation

Pillar: Chain — "The exponent is a chain of doublings. Each step either squares or squares-and-multiplies. Total: \(O(\log n)\) steps."

The Problem

Compute \(a^n \bmod m\) where \(n\) can be as large as \(10^{18}\).

The naive approach multiplies \(a\) by itself \(n\) times. That's \(O(n)\) multiplications. When \(n = 10^{18}\), even at \(10^9\) operations per second, you'd need a billion seconds. Roughly 30 years. Not happening.

You need an algorithm that handles exponents of \(10^{18}\) in under a millisecond. Binary exponentiation does it in at most 60 multiplications.

The Insight: Exponents Are Binary

Write the exponent in binary. Every positive integer is a sum of distinct powers of two. That decomposition turns one giant exponentiation into a short chain of squarings.

Take \(a^{13}\). In binary, \(13 = 1101_2 = 8 + 4 + 1\). So:

\[a^{13} = a^{8+4+1} = a^8 \cdot a^4 \cdot a^1\]

You don't need to compute \(a^{13}\) by multiplying \(a\) thirteen times. You need \(a^1\), \(a^2\), \(a^4\), \(a^8\) — each one is the square of the previous — and then you multiply together only the powers whose corresponding bit is \(1\).

The number \(n\) has \(\lfloor \log_2 n \rfloor + 1\) bits. You do one squaring per bit, and at most one extra multiplication per bit. That's \(O(\log n)\) total operations.

The Algorithm

Start with result = 1 and base = a. Scan the bits of \(n\) from least significant to most significant.

At each step:

  1. If the current bit is 1, multiply result by base.
  2. Square base (regardless of the bit value).
  3. Shift \(n\) right by one to move to the next bit.

After all bits are processed, result holds \(a^n \bmod m\).

The logic is direct: base tracks \(a^{2^k}\) at step \(k\). When bit \(k\) of \(n\) is set, you need that power in the product. When it's not, you skip it but still square base so it's ready for the next bit.

Trace: \(3^{13} \bmod 100\)

Binary of \(13\): \(1101_2\). We process bits from right to left (LSB first).

Step Bit base (before square) Action on result result base (after square)
0 1 \(3\) \(1 \times 3 = 3\) \(3\) \(3^2 = 9\)
1 0 \(9\) skip \(3\) \(9^2 = 81\)
2 1 \(81\) \(3 \times 81 = 243 \to 43\) \(43\) \(81^2 = 6561 \to 61\)
3 1 \(61\) \(43 \times 61 = 2623 \to 23\) \(23\) (done)

Result: \(3^{13} \bmod 100 = 23\).

Verify: \(3^{13} = 1{,}594{,}323\). And \(1{,}594{,}323 \bmod 100 = 23\). Correct.

Four steps. The naive approach would take 13 multiplications. For \(n = 10^{18}\), binary exponentiation takes at most 60 steps instead of \(10^{18}\).

The Code

Iterative

long long modpowIterative(long long base, long long exponent, long long mod) {
    long long result = 1;
    base %= mod;
    while (exponent > 0) {
        if (exponent & 1) {
            result = result * base % mod;
        }
        base = base * base % mod;
        exponent >>= 1;
    }
    return result;
}

Recursive

The recursive version splits the exponent in half at each call:

  • If \(n\) is even: \(a^n = (a^{n/2})^2\).
  • If \(n\) is odd: \(a^n = (a^{n/2})^2 \cdot a\).
long long modpowRecursive(long long base, long long exponent, long long mod) {
    if (exponent == 0) return 1;
    long long half = modpowRecursive(base, exponent / 2, mod);
    long long halfSquared = half * half % mod;
    if (exponent & 1) return halfSquared * (base % mod) % mod;
    return halfSquared;
}

Both produce identical results. The iterative version is preferred in practice — no recursion overhead, no stack depth concerns for large exponents.

Complexity: \(O(\log n)\) time, \(O(1)\) space (iterative) or \(O(\log n)\) stack space (recursive).

Why \(O(\log n)\)

The loop runs once per bit of \(n\). A number \(n\) has \(\lfloor \log_2 n \rfloor + 1\) bits. Each iteration does at most two modular multiplications (one for result *= base, one for base *= base). So the total work is at most \(2 \lfloor \log_2 n \rfloor + 2\) modular multiplications.

For \(n = 10^{18}\): \(\log_2(10^{18}) \approx 59.8\). That's at most 120 multiplications. Effectively instant.

Extension: Beyond Numbers

The same repeated-squaring trick works on anything with an associative binary operation. You don't need the elements to be integers — you need the operation to satisfy \((A \cdot B) \cdot C = A \cdot (B \cdot C)\).

Matrices. Replace scalar multiplication with matrix multiplication. Computing \(M^n\) for a \(k \times k\) matrix takes \(O(k^3 \log n)\) — \(O(\log n)\) matrix multiplications, each costing \(O(k^3)\). This is the backbone of solving linear recurrences in \(O(\log n)\). Ch10 L1 covers matrix exponentiation in detail.

Modular multiplication for huge moduli. When \(m > 3 \times 10^9\) and you can't use __int128, you can compute \(a \times b \bmod m\) using the same binary technique: decompose \(b\) into bits, double \(a\) at each step, and add when the bit is 1. This is sometimes called "binary multiplication" or "Russian peasant multiplication."

Common Mistakes

  • Forgetting mod at each step. Writing result = result * base and only taking mod at the end. By then, result has overflowed. Take mod after every multiplication: result = result * base % mod. Same for base = base * base % mod.

  • Not handling \(a^0 = 1\). The algorithm naturally returns \(1\) when exponent == 0 because result starts at \(1\) and the loop never executes. But if you modify the code and break this invariant, you'll silently return \(0\) for every zero-exponent query.

  • Overflow in base * base. If mod is close to \(2 \times 10^9\), then base can be up to \(\sim 2 \times 10^9\), and base * base reaches \(\sim 4 \times 10^{18}\), which fits in long long. But if mod exceeds \(3 \times 10^9\), the product overflows. Use (__int128)base * base % mod or switch to the binary multiplication technique.

Quick Recap

  • Binary exponentiation computes \(a^n \bmod m\) in \(O(\log n)\) by decomposing \(n\) into its binary bits and chaining squarings.
  • Iterative version: scan bits LSB to MSB. If bit is 1, multiply result by current base. Square base every step. Shift exponent right.
  • Take mod after every multiplication. Never let intermediate values overflow.
  • The modpow function is a building block used throughout this course — modular inverse (Ch4 L3), combinatorics (Ch5), matrix exponentiation (Ch10).
  • The same technique generalizes to any associative operation: matrices, polynomials, string hashing.

Problems

Problem Link Difficulty Focus
CSES — Exponentiation cses.fi/problemset/task/1095 Easy Direct application of modpow
LeetCode 50 — Pow(x, n) leetcode.com/problems/powx-n Medium Binary exponentiation with floating point and negative exponents
LeetCode 372 — Super Pow leetcode.com/problems/super-pow Medium Exponent given as an array of digits — chain modpow calls

Next lesson: Modular Inverse — computing \(a^{-1} \bmod m\) so that division works in modular arithmetic.