Pow(x, n)

Problem

Cryptographic protocols and physics simulations raise numbers to large powers millions of times per second. Naive repeated multiplication is O(n) and too slow for large exponents. Given a float x and integer n (which may be negative or zero), return x^n using the divide-and-conquer approach that runs in O(log n) time.

Input: x = 2.0,  n = 10   → 1024.0
Input: x = 2.0,  n = -3   → 0.125
Input: x = 2.0,  n = 0    → 1.0
Input: x = 3.0,  n = 4    → 81.0

Solution

Approach: Divide-and-conquer (fast / binary exponentiation) by halving the exponent.

The algorithm rests on one identity: x^n = (x^(n//2))^2, with one extra * x when n is odd (because integer division drops the remainder, so n//2 + n//2 = n - 1). Instead of multiplying x by itself n times, the function recurses once on the half-exponent, stores that result in half, and squares it - turning O(n) multiplications into O(log n) because the exponent is cut in half at every level. Storing half once and reusing it is what makes this fast: calling my_pow(x, n//2) twice would re-branch and lose the savings. The base case n == 0 returns 1.0, since any number to the zero power is 1. Negative exponents are peeled off first: x^(-n) = 1 / x^n, so the top guard recurses on -n and inverts the result, after which the rest of the function only ever sees non-negative exponents.

Trace my_pow(3.0, 4): n=4 even, recurse to n=2; n=2 even, recurse to n=1; n=1 odd, recurse to n=0 returning 1.0, then 1*1*3 = 3.0; back at n=2, 3*3 = 9.0; back at n=4, 9*9 = 81.0. Four recursive calls, not three naive multiplications.

Edge cases: n == 0 returns 1.0 (checked before any recursion). Negative n is handled by the n < 0 guard inverting a positive-exponent result, so my_pow(2.0, -3) = 0.125. A fractional or 1.0 base works unchanged since the recurrence is purely multiplicative.

Complexity: O(log n) time, O(log n) space - the exponent halves each call, so the recursion is log2(n) levels deep with one frame per level.