Chapter 23

Home

Fast Exponentiation

Computing ab naively takes O(b) multiplications. Fast exponentiation uses squaring to do it in O(log b).

The Naive Way

Multiplying a by itself b times is O(b). For b = 10¹⁸ that's impossible.

C++ — O(b)

long long slow_pow(long long a, long long b) {
    long long result = 1;
    for (long long i = 0; i < b; i++) {
        result = (result * a) % MOD;
    }
    return result;
}

Binary Exponentiation

The insight: ab = ab/2 × ab/2 (when b is even). Square the result and multiply by a when b is odd. This halves b each step.

3¹⁰ = 3⁵ × 3⁵ 3⁵ = 3² × 3² × 3 3² = 3 × 3 → 4 multiplications instead of 10

C++

long long mod_pow(long long a, long long b, long long m) {
    long long result = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) result = (result * a) % m;
        a = (a * a) % m;
        b >>= 1;  // b /= 2
    }
    return result;
}

b & 1 checks if b is odd. b >>= 1 divides by 2.

Rust

fn mod_pow(mut a: u64, mut b: u64, m: u64) -> u64 {
    let mut result = 1;
    a %= m;
    while b > 0 {
        if b & 1 == 1 {
            result = (result * a) % m;
        }
        a = (a * a) % m;
        b >>= 1;
    }
    result
}

💡 How it works

Each iteration halves b. For b = 10¹⁸, that's about 60 iterations instead of 10¹⁸. The b & 1 check handles odd powers by multiplying in an extra factor of a.

Key Takeaways

Practice