How Can I Implement a Power Function from Scratch, Handling Both Integer and Non-Integer Exponents?

Writing Your Own Power Function

Many programming languages include a power function, typically implemented as pow(double x, double y) in the standard library. However, understanding how to write this function from scratch can provide valuable insights.

Challenges

The primary challenge lies in handling non-integer exponents and negative powers. Simply looping until the desired power is reached is insufficient for these cases.

Solution

To address this, break the exponent into integer and rational parts. Calculate the integer power using a loop, taking advantage of factorization to optimize calculations. For the rational part, use an algorithm like bisection or Newton's method to approximate the root. Finally, multiply the results and apply the inverse if the exponent was negative.

Example

Consider the exponent -3.5. We decompose it into -3 (integer) and -0.5 (rational). Calculate 2^-3 using a loop, factoring 3 into 2 1. Then, approximate the root 2^(-0.5) using an iterative method. The final result, 1 / (8 * sqrt(2)), is obtained by multiplying and inverting the results.

Implementation

The following Python code demonstrates this approach:

def power(x, y):
    # Handle negative exponents
    if y < 0:
        return 1 / power(x, -y)

    # Decompose exponent
    int_part = int(y)
    rat_part = y - int_part

    # Calculate integer power using loop optimization
    res = 1
    while int_part > 0:
        if int_part % 2 == 1:
            res *= x
        x *= x
        int_part //= 2

    # Calculate fractional power using iterative approximation
    approx = x
    for i in range(1000):  # Iterative steps
        approx = (approx + x / approx) / 2

    # Multiply results and apply inverse if necessary
    result = res * approx
    return result if y > 0 else 1 / result

The above is the detailed content of How Can I Implement a Power Function from Scratch, Handling Both Integer and Non-Integer Exponents?. For more information, please follow other related articles on the PHP Chinese website!