Fast Power

Fast power (binary exponentiation) squares the base repeatedly and multiplies the running result only for set bits of the exponent.

Its core advantage:

x^n in O(log n) multiplications instead of O(n) — 3^1000000 needs ~20 steps, not a million.

Focus on recognizing:

Any repeated multiplication (power, matrix power, geometric term) = fast power

Core Template

public long power(long base, long exp) {
    return power(base, exp, Long.MAX_VALUE); // no mod
}

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

def power(base: int, exp: int, mod: int | None = None) -> int:
    if mod is not None:
        return pow(base, exp, mod)   # built-in — use it

    result = 1
    while exp > 0:
        if exp & 1:
            result *= base
        base *= base
        exp >>= 1
    return result

long long power(long long base, long long exp, long long mod = LLONG_MAX) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1)
            result = (__int128)result * base % mod;
        base = (__int128)base * base % mod;
        exp >>= 1;
    }
    return result;
}

function power(base, exp, mod = Infinity) {
  let result = 1n;
  base = BigInt(base) % BigInt(mod);
  const m = BigInt(mod);
  while (exp > 0n) {
    if (exp & 1n) result = (result * base) % m;
    base = (base * base) % m;
    exp >>= 1n;
  }
  return Number(result);
}

The loop reads the exponent’s bits LSB-first: odd → multiply result; always square the base.

Pattern 1: Modular Exponentiation

Watch 3^13 build bit by bit through 1101 — square every step, multiply only on set bits. Press ▶ to animate.

                        1
                        result = 1;  walk exponent bits LSB → MSB:
                      
                        2
                          result = result * result          // square
                      
                        3
                          if bit == 1: result = result * base
                      
                        4
                        log2(n) squarings instead of n multiplications
                      

The same loop with % mod at every step — this is how “answer mod 10^9+7” problems survive big exponents. Shown inline in the template above.

Fast power = read exponent bits + square-always + multiply-on-odd.

Common Mistakes

Forgetting base %= mod before the loop.

First squaring can overflow before any reduction happens.

Overflow inside the squaring.

In C++ with mod near 10^9, base * base exceeds 64 bits? No — (10^9)² ≈ 10^18 fits in long long, but larger mods need __int128. Java’s long is fine for 10^9-scale mods.

Recursing without need.

Iterative is shorter, faster, and stack-safe. Use recursion only when explaining the idea.

Complexity