Compute x^y for Floats and Negative Exponents: Fast Exponentiation

Compute x^y for Floats and Negative Exponents: Fast Exponentiation

Computing pow(x, y) efficiently is LeetCode #50 and a frequently-asked interview problem. The naive solution multiplies y times, which is O(y); the elegant solution uses fast exponentiation (binary exponentiation / repeated squaring) for O(log y). Interviewers also expect candidates to handle negative exponents, floating-point bases, integer overflow, and edge cases. This guide covers the standard approaches with working code, the recursive vs iterative variants, and the variations that come up as follow-ups.

Problem Statement

Implement pow(x, n), which computes x raised to the power n, without using language built-ins. Handle:

• x: floating-point base
• n: integer exponent (positive, negative, or zero)
• Edge cases: x = 0, n = 0, n < 0

Examples:

• pow(2.0, 10) → 1024.0
• pow(2.1, 3) → 9.261
• pow(2.0, -2) → 0.25
• pow(0.0, 5) → 0.0
• pow(1.0, 999) → 1.0

Approach 1: Naive Multiplication (O(n))

def my_pow_naive(x: float, n: int) -> float:
    """O(|n|) time, O(1) space."""
    if n < 0:
        x = 1 / x
        n = -n
    result = 1.0
    for _ in range(n):
        result *= x
    return result

Acceptable as a warm-up. For n = 2³¹, this is ~2 billion multiplications — too slow. Interviewers will push for O(log n).

Approach 2: Recursive Fast Exponentiation (Standard Answer)

Key insight: x^n = (x^(n/2))² if n is even; x × x^(n-1) if n is odd. Each recursion halves n.

def my_pow_recursive(x: float, n: int) -> float:
    """O(log |n|) time, O(log |n|) recursion stack."""
    if n < 0:
        return my_pow_recursive(1 / x, -n)
    if n == 0:
        return 1.0
    half = my_pow_recursive(x, n // 2)
    if n % 2 == 0:
        return half * half
    return half * half * x


# Tests
print(my_pow_recursive(2.0, 10))   # 1024.0
print(my_pow_recursive(2.1, 3))    # 9.261
print(my_pow_recursive(2.0, -2))   # 0.25
print(my_pow_recursive(1.0, 999))  # 1.0

Complexity: O(log |n|) time and O(log |n|) recursion stack space.

Why this works: 2^10 = (2^5)^2 = ((2^2 × 2)^2)^2. Each squaring step halves the remaining exponent. log₂(10) ≈ 3.3 squarings instead of 10 multiplications.

Approach 3: Iterative Fast Exponentiation

Same logic without recursion. Process the binary representation of n: for each bit, square the accumulator; if the bit is set, multiply by x.

def my_pow_iterative(x: float, n: int) -> float:
    """O(log |n|) time, O(1) space."""
    if n < 0:
        x = 1 / x
        n = -n
    result = 1.0
    while n > 0:
        if n & 1:
            result *= x
        x *= x
        n >>= 1
    return result

Complexity: O(log |n|) time, O(1) space — strictly better than recursive.

For interview purposes, either is acceptable. Iterative avoids the recursion-stack-depth concern; recursive reads more naturally for some.

Common Edge Cases

• n = 0. Any x raised to 0 is 1, including 0^0 (mathematically debated; most implementations return 1).
• x = 0 and n < 0. Division by zero. Either raise an exception or return infinity (depends on language convention).
• n = INT_MIN. Negating overflows for 32-bit integers; -INT_MIN > INT_MAX. In Python, no issue (arbitrary precision); in C++/Java, special-case it: use long or compute 1/x × my_pow(x, -(n+1)).
• Very large n. 2^(2^31) overflows float; but the algorithm doesn’t care about overflow during the computation itself in IEEE-754. Handle infinity sensibly if asked.
• x = 1 or x = -1. Result is always 1 or ±1; don’t compute n iterations. Some implementations short-circuit these for efficiency, but the asymptotic gain is negligible.

Common Variations

Modular exponentiation

Compute x^n mod m. Same fast-exp algorithm with mod after every multiplication. Used in cryptography (RSA, Diffie-Hellman) and number theory.

def mod_pow(x: int, n: int, m: int) -> int:
    """O(log n) modular exponentiation."""
    result = 1
    x %= m
    while n > 0:
        if n & 1:
            result = (result * x) % m
        x = (x * x) % m
        n >>= 1
    return result

Python’s built-in pow(x, n, m) does this directly with the optional third argument.

Matrix exponentiation

Compute M^n for a square matrix M. Same algorithm; replace scalar multiplication with matrix multiplication. Used in solving linear recurrences (Fibonacci in O(log n) time).

Square root via fast exponentiation

Inverse problem: compute x^(1/2). Use Newton’s method or bisection rather than fast exp; fast exp is for integer exponents specifically.

Fast Fibonacci

F(n) = matrix-power applied to [[1,1],[1,0]]^n. O(log n) time using matrix fast-exp. Substantially faster than naive O(n) iteration for very large n (n > 10^6).

Common Mistakes

• Recomputing x^(n/2) twice. A naive recursive version computing my_pow(x, n/2) * my_pow(x, n/2) for even n is O(n) instead of O(log n). Always store the recursive call in a variable and reuse.
• Floating-point precision drift. Repeated squaring of imperfect floats accumulates error. For high-precision requirements, use decimal.Decimal in Python or arbitrary-precision libraries. For typical interview answers, IEEE-754 is fine.
• Wrong handling of negative n. The standard pattern: convert x to 1/x and negate n. Forgetting this causes incorrect results for negative exponents.
• Integer overflow on negation. In C++/Java, -INT_MIN overflows. Special-case it or use a wider type. Python doesn’t have this issue.
• Forgetting the n = 0 base case. Without it, recursive version doesn’t terminate. Always include if n == 0: return 1.
• Returning int when float is expected. pow(2.0, 10) should return 1024.0, not 1024. Use 1.0 as the initial result and float arithmetic throughout.

Frequently Asked Questions

See also: Check if a Number Is a Power of Two • Two Sum: Find a Pair in an Array • Detect a Cycle in a Linked List

pow(2, 5) = 2 * 2 * 2 * 2 * 2

pow(x, 8) = pow(x, 4) * pow(x, 4)
pow(x, 4) = pow(x, 2) * pow(x, 2)
pow(x, 2) = x * x

pow(x, 9) = x * pow(x, 8)

result = 1
2^1 = 2 (bit 0 is 1) → result = 2
2^2 = 4 (bit 2 is 0) → result = 2
2^4 = 16 (bit 3 is 1) → result = 2 * 16 = 32
2^8 = 256 (bit 4 is 1) → result = 32 * 256 = 8192

function pow(x, y) {
    // Handle edge cases first

    // 0^0 is undefined, but conventionally return 1
    if (x === 0 && y === 0) return 1;

    // 0^positive = 0
    if (x === 0 && y > 0) return 0;

    // 0^negative = infinity (undefined)
    if (x === 0 && y < 0) return Infinity;

    // x^0 = 1 for any x
    if (y === 0) return 1;

    // 1^y = 1 for any y
    if (x === 1) return 1;

    // (-1)^y alternates between 1 and -1 for integers
    if (x === -1) {
        return y % 2 === 0 ? 1 : -1;
    }

    // Handle negative base with fractional exponent (complex result)
    if (x < 0 && !Number.isInteger(y)) {
        return NaN; // Would be complex number
    }

    // For floating point exponents, use logarithms
    if (!Number.isInteger(y)) {
        // x^y = e^(y * ln(x))
        if (x < 0) return NaN; // Already checked above
        return Math.exp(y * Math.log(Math.abs(x)));
    }

    // From here, y is an integer

    // Handle negative exponent: x^(-y) = 1 / x^y
    let isNegativeExp = y < 0;
    y = Math.abs(y);

    // Fast exponentiation (iterative)
    let result = 1;
    let base = x;

    while (y > 0) {
        // If current bit is 1, multiply result by current base
        if (y % 2 === 1) {
            result *= base;
        }

        // Square the base for next bit
        base *= base;

        // Shift to next bit
        y = Math.floor(y / 2);
    }

    // Apply negative exponent if needed
    if (isNegativeExp) {
        result = 1 / result;
    }

    return result;
}

// Test cases
console.log(pow(2, 10));        // 1024
console.log(pow(2, -3));        // 0.125 (1/8)
console.log(pow(-2, 3));        // -8
console.log(pow(-2, 4));        // 16
console.log(pow(2, 0.5));       // 1.414... (sqrt(2))
console.log(pow(0, 0));         // 1 (by convention)
console.log(pow(0, 5));         // 0
console.log(pow(0, -1));        // Infinity
console.log(pow(-2, 0.5));      // NaN (complex number)
console.log(pow(1.5, 3));       // 3.375

import math

def pow(x, y):
    # Edge cases
    if x == 0 and y == 0:
        return 1
    if x == 0:
        return 0 if y > 0 else float('inf')
    if y == 0:
        return 1
    if x == 1:
        return 1
    if x == -1:
        return 1 if int(y) % 2 == 0 else -1

    # Negative base with fractional exponent
    if x < 0 and not float(y).is_integer():
        return float('nan')

    # Floating point exponent
    if not float(y).is_integer():
        return math.exp(y * math.log(abs(x)))

    # Integer exponentiation
    is_negative = y < 0
    y = abs(int(y))

    result = 1
    base = x

    while y > 0:
        if y & 1:  # Check if odd (bit is 1)
            result *= base
        base *= base
        y >>= 1  # Right shift (divide by 2)

    return 1 / result if is_negative else result


# Test all edge cases
test_cases = [
    (2, 10, 1024),
    (2, -3, 0.125),
    (-2, 3, -8),
    (-2, 4, 16),
    (2, 0.5, math.sqrt(2)),
    (0, 0, 1),
    (0, 5, 0),
    (3.5, 2, 12.25),
]

for x, y, expected in test_cases:
    result = pow(x, y)
    print(f"pow({x}, {y}) = {result} (expected ~{expected})")