Pow(x, n)

Problem

Compute x raised to the integer power n, where x is a floating-point number and n may be negative, zero, or positive. Do it in time logarithmic in |n|.

• x is a small magnitude float, well under 100 in absolute value.
• n fits in a signed 32-bit int, so it can be as negative as -2^31.
• Either x is non-zero or n is positive, so 0^0 and division by zero do not arise.
• The result is guaranteed to fit in a 64-bit float; answers within 1e-5 of the true value are accepted.

Examples

• x = 3.0, n = 7 → 2187.0.
• x = 3.0, n = -2 → 0.1111..., since 3^-2 = 1 / 3^2.
• x = 2.0, n = -2147483648 → 0.0; 2^-2147483648 underflows to zero. The magnitude 2^31 does not fit in a signed 32-bit int, which is the trap in languages with fixed-width integers.

Hints

1. Multiplying x by itself n times is O(n). For n = 2^31 that is billions of multiplications. Can you reuse work?
2. x^n = (x^(n/2))^2 when n is even, and x * (x^(n/2))^2 when odd. How deep does that recursion go?
3. Fast exponentiation (exponentiation by squaring), recursively or by iterating over the bits of n. Handle negative n by inverting x and negating n first.