Implement `fast_power(x, n)` without calling a built-in exponentiation routine. `n` is a signed 32-bit integer and may be negative. Return `x` raised to the power `n`. A zero exponent returns `1`. For a negative exponent, compute the reciprocal of the corresponding positive power. Inputs for which the mathematical result is undefined, such as zero raised to a negative exponent, are outside this task. Your algorithm should use `O(log |n|)` multiplications and must remain correct when `n` is the minimum signed 32-bit integer, whose positive magnitude cannot be represented in the same type. For example, `fast_power(2, -3)` returns `0.125`. ```hint Halve the exponent After separating the sign, square the base while repeatedly halving the exponent. An odd exponent contributes the current base to the result. ``` ```hint Widen before negating Convert the exponent to a wider signed type before taking the magnitude so the minimum 32-bit value does not overflow. ``` ### Discussion Extensions - Compare recursive exponentiation by squaring with an iterative implementation. - Explain the time complexity of both versions and the extra stack space used by recursion.