Module 15 · Recursion and Divide-and-Conquer

145. Fast Exponentiation

Bridge · Download this solution · All solutions and shared helpers

Problem

Compute x raised to integer exponent n using recursive exponentiation by squaring. Return a floating-point result. Negative exponents require x!=0; define x**0 as 1.0, including x=0. Ordinary floating-point rounding and range limits apply.

Examples

Example 1

fast_power(2, 10)
=> 1024.0

Repeated squaring replaces ten linear multiplications with logarithmic depth.

Example 2

fast_power(2, -3)
=> 0.125

The reciprocal base handles a negative exponent.

Example 3

fast_power(0, 0)
=> 1.0

The contract explicitly uses the exponent-zero identity.

Reveal the worked solution and reasoning

Why this mechanism works

If the exponent is even, x^n=(x^(n//2))^2. If odd, multiply that square by one additional x. Compute the half power once and reuse it; making two identical recursive calls would undo the logarithmic work reduction. A negative exponent first inverts the base.

State and boundaries

Each call returns the requested power. half is the single result of the exponent-halved child call.

Protocol

For a negative exponent invert x and negate n.
Return 1.0 at exponent zero.
Recursively compute the half power once.
Square it.
Multiply by x only for an odd exponent.

Visualization

2^10 -> (2^5)^2
2^5 -> (2^2)^2 * 2
2^2 -> (2^1)^2
one child call per level

Python implementation

def fast_power(x, n):
    if n < 0:
        return fast_power(1 / x, -n)
    if n == 0:
        return 1.0
    half = fast_power(x, n // 2)
    result = half * half
    return result * x if n % 2 else result

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

fast_power(2, 10)

L2 fast_power: if n < 0:
x=2; n=10

L2 fast_power: if n < 0:
x=2; n=5

L2 fast_power: if n < 0:
x=2; n=2

L2 fast_power: if n < 0:
x=2; n=1

L2 fast_power: if n < 0:
x=2; n=0

L6 fast_power: half = fast_power(x, n // 2)
x=2; n=1; half=1.0

L7 fast_power: result = half * half
x=2; n=1; half=1.0; result=1.0

L6 fast_power: half = fast_power(x, n // 2)
x=2; n=2; half=2.0

... 1 intermediate state changes omitted ...

L6 fast_power: half = fast_power(x, n // 2)
x=2; n=5; half=4.0

L7 fast_power: result = half * half
x=2; n=5; half=4.0; result=16.0

L6 fast_power: half = fast_power(x, n // 2)
x=2; n=10; half=32.0

L7 fast_power: result = half * half
x=2; n=10; half=32.0; result=1024.0

Result: 1024.0. Repeated squaring replaces ten linear multiplications with logarithmic depth.

fast_power(2, -3)

L2 fast_power: if n < 0:
x=2; n=-3

L2 fast_power: if n < 0:
x=0.5; n=3

L2 fast_power: if n < 0:
x=0.5; n=1

L2 fast_power: if n < 0:
x=0.5; n=0

L6 fast_power: half = fast_power(x, n // 2)
x=0.5; n=1; half=1.0

L7 fast_power: result = half * half
x=0.5; n=1; half=1.0; result=1.0

L6 fast_power: half = fast_power(x, n // 2)
x=0.5; n=3; half=0.5

L7 fast_power: result = half * half
x=0.5; n=3; half=0.5; result=0.25

Result: 0.125. The reciprocal base handles a negative exponent.

Why the solution is correct

The zero exponent is the multiplicative identity. The even and odd exponent identities combine a correct smaller power into the requested one. Halving a positive exponent reaches zero, and the reciprocal identity handles negative exponents.

Time and space

O(log(|n|+1)) multiplications and call-stack depth, excluding floating-point implementation details.

Common mistakes

Calling the same half-power recursion twice creates a much larger call tree. Negating n without inverting x computes the wrong negative power.

Reasoning card

State: Each call returns the requested power. half is the single result of the exponent-halved child call.

Invariant: The returned value equals the requested exponent for that call.

Decision to rehearse: Square a half-power rather than multiplying n times.

Finish: Multiply by x only for an odd exponent

Transfer exercise

Compute modular powers with integer arithmetic and reduce after each multiplication; discuss why negative exponents need a modular inverse.