Fast Exponentiation

Fast exponentiation computes powers by repeatedly squaring instead of multiplying one copy at a time.

It reduces exponentiation from linear in the exponent to logarithmic in the exponent.

Core Idea

The exponent is processed through its binary representation. When the current bit is set, the result is multiplied by the current base. Each step squares the base and halves the exponent.

This works especially well with modular arithmetic.

Function Contract

power_mod(base, exponent, mod) expects a non-negative integer exponent and a positive modulus.

It returns (base ** exponent) % mod using repeated squaring. In Python, pow(base, exponent, mod) provides the same operation efficiently.

Python Example

def power_mod(base, exponent, mod):
    result = 1
    base %= mod
 
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exponent //= 2
 
    return result

Python’s built-in pow(base, exponent, mod) performs modular exponentiation efficiently.

Step-by-Step Example

To compute 3^13, use the binary form of 13:

13 = 8 + 4 + 1

Repeated squaring builds 3^1, 3^2, 3^4, 3^8. The result multiplies the powers corresponding to set bits: 3^8 * 3^4 * 3^1.

Why It Works

Every exponent can be written in binary. Squaring moves from base^(2^k) to base^(2^(k+1)). When a binary bit is present, that power contributes to the final answer.

Complexity

The loop halves the exponent each time, so it runs O(log exponent) iterations. With a modulus, numbers stay bounded by the modulus.

Pattern Beyond Powers

Fast exponentiation is really a repeated-squaring pattern. It can apply to any associative operation where “squaring” means combining a value with itself, such as matrix multiplication.

That is why the same idea appears again in matrix exponentiation.

Failure Example

A loop that multiplies the base exponent times is linear in the exponent. That may be impossible when the exponent is extremely large.

Fast exponentiation is useful because each loop step halves the remaining exponent.

Common Confusions

Fast exponentiation is not only for very large bases. The key is a large exponent.

When a modulus is involved, applying % mod during the loop prevents numbers from becoming unnecessarily huge.

Another common mistake is using repeated multiplication for a massive exponent. That is linear in the exponent and often too slow.

When To Use It

Use fast exponentiation for modular powers, repeated doubling-like transitions, cryptography-adjacent arithmetic, and recurrence acceleration patterns.

Do not implement it manually in Python when pow(base, exponent, mod) is acceptable. Study the algorithm to understand the pattern.

The Main Point

Fast exponentiation uses binary decomposition of the exponent to replace repeated multiplication with repeated squaring.