Pow(x, n)

Implement pow(x, n) which calculates x raised to the power n. A naive loop is too slow for large |n|.

Why this is worth learning

Write the exponent in binary. Squaring moves to the next power-of-two contribution, and an odd low bit says to multiply that contribution into the result.

Before coding: one-minute experiment

For exponent 13, which powers of the base are multiplied into the answer? Why widen before negating -2147483648?

Function signature

func MyPow(x float64, n int) float64

Inputs / outputs

• x: base.
• n: exponent (can be negative).
• Return: x^n.

Example

2^10 = 1024
2^-2 = 0.25

Constraints

• -2^31 <= n <= 2^31 - 1

Core idea (near-solution)

Multiplying x by itself |n| times is a direct model but is impractical at the allowed exponent limit. Squaring replaces two copies of a factor by one larger factor. The binary expansion of n tells which of those powers are needed: 13=8+4+1. A result accumulator plus a current squared base and remaining exponent preserves exactly the work still owed, rather than remembering every multiplication.

Use binary (fast) exponentiation. Repeatedly square the base and use the bits of n to decide when to multiply into the result.

Invariant: after negative-exponent normalization, res * base^remaining equals the requested power in exact arithmetic. The mutable base is repeatedly squared; it is not the original x. Float64 operations round this identity.

Algorithm (step-by-step)

1. Convert n to int64 to handle INT_MIN safely.
2. If n < 0, set x = 1/x and n = -n.
3. Initialize result = 1.
4. While n > 0:
   • If n is odd, result *= x.
   • x *= x, n >>= 1.
5. Return result.

Correctness sketch

After handling a negative exponent by reciprocating the base, maintain result * base^exp equal to the desired power in exact arithmetic. If exp is odd, multiply one base into result; the remaining even exponent can be halved while squaring base. If exp is even, square and halve directly. Thus the invariant is preserved and exp decreases to zero in logarithmically many shifts. The exponent is widened to int64 before negating, so the minimum signed-32-bit exponent can be represented positively. Actual float64 multiplication rounds, so the arithmetic identity describes the algorithm, not exact real-number output for every input.

Trace (hand walkthrough)

Example input:
2^10 = 1024
2^-2 = 0.25

Walk:
- 2^10: n=10 even -> x=4; n=5 odd -> res=4, x=16; n=2 -> x=256; n=1 -> res=1024
- 2^-2: invert x=0.5, n=2 -> x=0.25, n=1 -> res=0.25

Pitfalls to avoid

• Overflow when negating INT_MIN (use int64).
• Forgetting to invert x for negative exponents.

Debugging lens

Test exponent zero, negative exponents, base -1 with odd/even exponents, and the minimum allowed exponent. Do not promise finite results for arbitrary bases: float overflow, underflow, and division by zero follow floating-point behavior.

Complexity

• Time: O(log |n|).
• Extra space: O(1).

Implementation notes (Go)

• Use int64 for the exponent to safely negate n.

Contract precision

The exponent is restricted to signed 32-bit range even though its Go type is int. The reference returns 1 for exponent zero, including base zero. Negative powers of zero and nonfinite/overflowing inputs follow Go floating-point operations, not an error-return API.

Reconstruction checkpoint

For exponent 13, which powers of the base are multiplied into the answer? Why widen before negating -2147483648?

Return to Math · Module quiz