15.8 Fast Exponentiation

Problem

You need to compute:

$$ x^n $$

where (n) is a nonnegative integer.

The direct method multiplies (x) by itself (n) times:

x * x * x * ... * x

This takes:

$$ O(n) $$

multiplications.

For small exponents this is fine. For large exponents, especially in modular arithmetic, cryptography, combinatorics, and numerical code, linear exponentiation is too slow.

Can divide and conquer reduce the number of multiplications?

Solution

Use fast exponentiation, also called exponentiation by squaring.

The key identity is:

$$ x^n = \begin{cases} (x^{n/2})^2, & \text{if } n \text{ is even} \\nx \cdot x^{n-1}, & \text{if } n \text{ is odd} \end{cases} $$

Instead of reducing the exponent by one at each step, the algorithm cuts it roughly in half.

That changes the running time from:

$$ O(n) $$

to:

$$ O(\log n) $$

A Small Example

Compute:

3^13

The naive method performs 12 multiplications.

Fast exponentiation uses the binary structure of the exponent:

3^13 = 3 * 3^12
     = 3 * (3^6)^2
     = 3 * ((3^3)^2)^2
     = 3 * ((3 * 3^2)^2)^2

A cleaner way to see it is through repeated squaring:

3^1  = 3
3^2  = 9
3^4  = 81
3^8  = 6561

Since:

13 = 8 + 4 + 1

we combine:

3^13 = 3^8 * 3^4 * 3^1

The algorithm uses only logarithmically many squaring steps.

Recursive Implementation

func Pow(x int64, n int64) int64 {
    if n == 0 {
        return 1
    }

    half := Pow(x, n/2)

    if n%2 == 0 {
        return half * half
    }

    return x * half * half
}

This implementation follows the mathematical recurrence directly.

For example:

fmt.Println(Pow(3, 13))

Output:

1594323

Recurrence Analysis

Each recursive call halves the exponent.

The recurrence is:

$$ T(n)=T(n/2)+O(1) $$

The recursion depth is:

$$ \log_2 n $$

Each level performs a constant number of multiplications.

Therefore:

$$ T(n)=O(\log n) $$

This is one of the simplest and most useful divide-and-conquer speedups.

Avoiding Duplicate Work

A common mistake is writing:

func BadPow(x int64, n int64) int64 {
    if n == 0 {
        return 1
    }

    if n%2 == 0 {
        return BadPow(x, n/2) * BadPow(x, n/2)
    }

    return x * BadPow(x, n/2) * BadPow(x, n/2)
}

This looks like divide and conquer, but it recomputes the same subproblem twice.

The recurrence becomes:

$$ T(n)=2T(n/2)+O(1) $$

which gives:

$$ O(n) $$

The efficient version stores the recursive result once:

half := Pow(x, n/2)

That line is the difference between logarithmic and linear behavior.

Iterative Implementation

The iterative version is often preferred in production. It avoids recursion and follows the binary representation of the exponent.

func PowIter(x int64, n int64) int64 {
    result := int64(1)
    base := x
    exp := n

    for exp > 0 {
        if exp%2 == 1 {
            result *= base
        }

        base *= base
        exp /= 2
    }

    return result
}

The loop invariant is:

result * base^exp == x^n

At each step:

• If exp is odd, we consume one factor of base.
• We square base.
• We halve exp.

When exp becomes zero, the invariant gives:

result == x^n

Binary View

Consider:

13 = 1101₂

The set bits correspond to powers:

13 = 8 + 4 + 1

So:

x^13 = x^8 * x^4 * x

The iterative algorithm walks through these bits from least significant to most significant.

For:

exp = 13

the steps are:

exp	bit odd?	result	base
13	yes	x	x
6	no	x	x²
3	yes	x * x⁴	x⁴
1	yes	x * x⁴ * x⁸	x⁸
0	stop	x¹³	x¹⁶

The table shows why the algorithm works: every bit of the exponent determines whether the current power of the base contributes to the final product.

Modular Exponentiation

Fast exponentiation is most often used with a modulus.

Instead of computing:

$$ x^n $$

directly, compute:

$$ x^n \bmod m $$

This prevents enormous intermediate values.

func ModPow(x, n, mod int64) int64 {
    if mod == 1 {
        return 0
    }

    result := int64(1)
    base := x % mod
    exp := n

    for exp > 0 {
        if exp%2 == 1 {
            result = (result * base) % mod
        }

        base = (base * base) % mod
        exp /= 2
    }

    return result
}

Example:

fmt.Println(ModPow(3, 13, 17))

Output:

12

This is the foundation of many algorithms in number theory and cryptography.

Matrix Exponentiation

The same idea works for any associative operation, not only numeric multiplication.

If matrix multiplication is available, fast exponentiation can compute:

$$ A^n $$

in:

$$ O(\log n) $$

matrix multiplications.

This is useful for linear recurrences.

For example, Fibonacci numbers can be computed using:

$$ \begin{bmatrix} 1 & 1 \\n1 & 0 \end{bmatrix}^n $$

The exponentiation framework stays the same. Only the multiplication operation changes.

General Pattern: Exponentiation by Monoid

Fast exponentiation works whenever we have:

• an associative binary operation
• an identity element

This structure is called a monoid.

For numbers under multiplication:

operation: *
identity: 1

For matrices under multiplication:

operation: matrix multiply
identity: identity matrix

For strings under concatenation:

operation: concatenate
identity: empty string

For function composition:

operation: compose
identity: identity function

The algorithm is not really about integers. It is about repeated application of an associative operation.

Generic Implementation Idea

In a language with generics, the structure is:

pow(base, exponent, identity, multiply)

Pseudo-code:

result = identity

while exponent > 0
    if exponent is odd
        result = multiply(result, base)

    base = multiply(base, base)
    exponent = exponent / 2

return result

This turns repeated multiplication into a reusable algorithmic pattern.

Handling Negative Exponents

For ordinary integer exponentiation, negative exponents are not closed over integers:

2^-3 = 1/8

If using floating-point numbers, one can define:

func PowFloat(x float64, n int64) float64 {
    if n < 0 {
        return 1.0 / PowFloat(x, -n)
    }

    result := 1.0
    base := x
    exp := n

    for exp > 0 {
        if exp%2 == 1 {
            result *= base
        }

        base *= base
        exp /= 2
    }

    return result
}

For modular arithmetic, negative exponents require modular inverses. This only works when the base is invertible modulo (m).

Common Mistakes

Recomputing the Half Power

Calling the same recursive function twice destroys the performance gain.

Always store the half result.

Forgetting the Identity Case

The base case must return:

1

for ordinary multiplication.

For generic exponentiation, it must return the identity element of the operation.

Overflowing Integers

Even fast exponentiation does not prevent overflow.

For large integer powers, use modular exponentiation or arbitrary-precision integers.

Mishandling Negative Exponents

Integer exponentiation usually does not support negative exponents.

Decide explicitly whether the result type is integer, rational, floating point, or modular.

Confusing % 2 with Division

In the iterative method:

if exp%2 == 1

tests whether the current binary bit is set.

Then:

exp /= 2

shifts the exponent right by one bit.

Both operations are required.

Discussion

Fast exponentiation is a compact example of divide and conquer at its best. The direct algorithm removes one factor at a time. The improved algorithm uses the algebraic identity (x^{2k}=(x^k)^2) to cut the remaining work in half at every step.

The result is not merely faster code. It changes the class of problems we can solve comfortably. Modular exponentiation with billion-sized exponents becomes routine. Matrix powers become practical. Recurrences can be advanced by large time steps. Cryptographic protocols rely on exactly this kind of logarithmic scaling.

The deeper lesson is that divide and conquer often comes from finding a reusable intermediate result. Once (x^{n/2}) has been computed, using it twice costs one multiplication, not another recursive computation. That principle appears throughout efficient algorithm design: compute the expensive part once, then reuse it in a structure that preserves correctness.