Implement pow(x, n) with fast exponentiation

Compute x raised to an integer power n, which may be negative, using O(log |n|) multiplications instead of multiplying n times.

Interface

Unless you agree on a different interface with the interviewer, assume:

• my_pow(x: float, n: int) -> float — no use of the language's power operator or library.

Example

my_pow(2.0, 10)   ->  1024.0
my_pow(2.1, 3)    ->  9.261 (up to floating-point rounding)
my_pow(2.0, -2)   ->  0.25
my_pow(5.0, 0)    ->  1.0
my_pow(-2.0, 3)   ->  -8.0

Constraints

• -100 < x < 100; n is a 32-bit signed integer, so n can be -2^31.
• x is not zero when n is negative.

Clarifying questions

• Can n be negative, and what about n = 0 or x = 0?
• How should n = -2^31 be handled in a language where -n overflows?
• What precision is expected?
• Recursive or iterative?

What a strong answer covers

• Exponentiation by squaring: x^n = (x^(n/2))^2, times x when n is odd. O(log |n|) time.
• The iterative version over the bits of n: square the base each step, multiply into the result when the low bit is set; O(1) space.
• Negative exponents: compute with |n| and take the reciprocal; widen n to 64 bits first so -(-2^31) doesn't overflow.
• Edge cases: n = 0, x = 1 or -1, x = 0, very large |n| where the result underflows to 0.
• Tests against a reference on a table of cases.

Follow-ups

• Modular exponentiation x^n mod m for integers.
• Raise a matrix to a power (and compute Fibonacci numbers in O(log n)).
• Compute the integer square root without library calls.