← Math & Geometry

Drill #121 — Pow(x, n)

Medium Fast Exponentiation Math & Geometry

In plain English: Compute x to the power n efficiently, handling negative exponents too.

Binary exponentiation: if n is even, x^n = (x^(n/2))^2. If n is odd, x^n = x * x^(n-1). This halves the exponent each step, giving O(log n) multiplications instead of O(n).

Try to write it from scratch before scrolling down.

def my_pow(x, n):
    if n < 0:
        x = 1 / x
        n = -n
    result = 1
    while n:
        if n & 1:         # odd exponent
            result *= x
        x *= x            # square the base
        n >>= 1           # halve the exponent
    return result

# Test: my_pow(2.0, 10) == 1024.0
# Test: my_pow(2.0, -2) == 0.25