DSA Pow(x, n)

The problem

Pow(x, n) raises a number x to an integer power n. A positive power multiplies x by itself n times. A negative power divides 1 by the positive power.

The base x may be a fraction or a negative number. The answer is a number, and the article counts the multiplications behind it.

cases = [
    (2, 10, 1024.0),
    (2, -2, 0.25),
    (1.5, 3, 3.375),
    (5, 0, 1.0),
    (4, -2, 0.0625),
    (-2, 3, -8.0),
    (-2, 2, 4.0),
]
for x, n, expected in cases:
    print(x, "to the", n, "=", expected)

Read the last two rows together. The base -2 stays negative under an odd power. It turns positive under an even power.

Intuition: multiply x by itself n times

The first idea starts from 1. It multiplies by x once per unit of the exponent. The method needs no insight, and it works for every positive exponent.

result = 1.0
steps = 0
for _ in range(10):
    result *= 2
    steps += 1
print("2 to the 10th:", result)
print("multiplications:", steps)

Ten multiplications is a small price here. The price grows in a straight line with the exponent. A large exponent makes the plain loop do large, mostly wasted work.

Brute force: the counted plain loop

The brute force is the intuition, written as a function. Its counter rises once per multiplication. It handles a positive exponent only, and the optimal section adds the sign handling.

def power_brute(x, n):
    result = 1.0
    steps = 0
    for _ in range(n):
        result *= x
        steps += 1
    return result, steps

for n in [10, 50, 100]:
    value, steps = power_brute(2, n)
    print("2 to the", n, "- multiplications:", steps, "digits:", len(str(int(value))))

The counter tells the whole story. The multiplications equal the exponent, every time. Squaring can cut that count down to the number of bits in the exponent.

The optimal solution: square the base, halve the exponent

The method squares the base on each loop pass and multiplies the running result by the base only when the current exponent bit is 1, and a negative exponent first replaces the base with its reciprocal and flips the exponent sign.

That sign handling is the source lesson's rule. The loop then runs on a positive exponent only. An exponent of zero returns 1 before any loop runs.

def my_pow(x, n):
    steps = 0
    if n == 0:
        return 1.0, steps
    base = x
    exp = n
    if exp < 0:
        base = 1.0 / x
        exp = -exp
    result = 1.0
    while exp > 0:
        if exp & 1:
            result *= base
            steps += 1
        base *= base
        steps += 1
        exp = exp >> 1
    return result, steps

cases = [
    (2, 10, 1024.0),
    (2, -2, 0.25),
    (1.5, 3, 3.375),
    (5, 0, 1.0),
    (4, -2, 0.0625),
    (-2, 3, -8.0),
    (-2, 2, 4.0),
]
for x, n, expected in cases:
    value, steps = my_pow(x, n)
    print(x, "to the", n, "=", value, "| multiplications:", steps, "| matches **:", value == x ** n, "| expected:", expected)

All seven cases from the start of the article pass. Each answer also matches the ** operator. The multiplication counts stay in single digits here.

Walkthrough: 2 to the 10th, bit by bit

The exponent 10 is 1010 in binary. The walk prints the state after each loop pass. The result takes the base only on passes where the lowest bit is 1.

x = 2
n = 10
result = 1.0
base = float(x)
exp = n
print("start: result", result, "base", base, "exp", exp)
while exp > 0:
    bit = exp & 1
    if bit:
        result *= base
    print("bit", bit, "-> result", result, "next base", base * base, "next exp", exp >> 1)
    base *= base
    exp = exp >> 1
print("answer:", result)

The result picks up the base twice, on the two passes with bit 1. It takes 4 on the second pass and 256 on the fourth pass. Their product is the answer, 1024.

Complexity

The fast loop halves the exponent on every pass, so its time is O(log n). It holds only the result, the base, and a counter, so its extra space is O(1).

def my_pow(x, n):
    steps = 0
    if n == 0:
        return 1.0, steps
    base = x
    exp = n
    if exp < 0:
        base = 1.0 / x
        exp = -exp
    result = 1.0
    while exp > 0:
        if exp & 1:
            result *= base
            steps += 1
        base *= base
        steps += 1
        exp = exp >> 1
    return result, steps

def power_brute_steps(n):
    return n

for n in [10, 100, 1000]:
    value, steps = my_pow(2, n)
    print("exponent", n, "- brute multiplications:", power_brute_steps(n), " fast multiplications:", steps)

The brute count grows with the exponent itself. The fast count grows with the bit length of the exponent. At exponent 1000 the gap is already wide.

Edge cases and pitfalls

A loop written as range(n) runs zero times for a negative n. Without the sign handling, a negative power would wrongly return 1. The block below shows that failure and the fixed answers side by side.

def broken_pow(x, n):
    result = 1.0
    for _ in range(n):
        result *= x
    return result

def my_pow(x, n):
    steps = 0
    if n == 0:
        return 1.0, steps
    base = x
    exp = n
    if exp < 0:
        base = 1.0 / x
        exp = -exp
    result = 1.0
    while exp > 0:
        if exp & 1:
            result *= base
            steps += 1
        base *= base
        steps += 1
        exp = exp >> 1
    return result, steps

print("broken 2 to the -3:", broken_pow(2, -3))
print("fixed 2 to the -3:", my_pow(2, -3)[0])
print("exponent zero:", my_pow(7, 0)[0])
print("base zero, positive power:", my_pow(0, 5)[0])
print("base one, negative power:", my_pow(1, -4)[0])
print("negative base, odd power:", my_pow(-2, 3)[0])
print("negative base, even power:", my_pow(-2, 2)[0])
print("fraction base:", my_pow(1.5, 3)[0])

Zero to a negative power has no answer here. It would divide by zero, and the source lesson never asks for it. Every other sign case runs through the one reciprocal step.