Alex Rivera | Logout

How can I write a power function myself?

Asked 2010-05-21T14:01:53.107
54

I was always wondering how I can make a function which calculates the power (e.g. 23) myself. In most languages these are included in the standard library, mostly as pow(double x, double y), but how can I write it myself?

I was thinking about for loops, but it think my brain got in a loop (when I wanted to do a power with a non-integer exponent, like 54.5 or negatives 2-21) and I went crazy ;)

So, how can I write a function which calculates the power of a real number? Thanks

Oh, maybe important to note: I cannot use functions which use powers (e.g. exp), which would make this ultimately useless.

c++ math floating-point
Edit
Report

1 Answer

9

There are two distinct cases to deal with: Integer exponents and fractional exponents.

For integer exponents, you can use exponentiation by squaring.

def pow(base, exponent):
    if exponent == 0:
        return 1
    elif exponent < 0:
        return 1 / pow(base, -exponent)
    elif exponent % 2 == 0:
        half_pow = pow(base, exponent // 2)
        return half_pow * half_pow
    else:
        return base * pow(base, exponent - 1)

The second "elif" is what distinguishes this from the naïve pow function. It allows the function to make O(log n) recursive calls instead of O(n).

For fractional exponents, you can use the identity a^b = C^(b*log_C(a)). It's convenient to take C=2, so a^b = 2^(b * log2(a)). This reduces the problem to writing functions for 2^x and log2(x).

The reason it's convenient to take C=2 is that floating-point numbers are stored in base-2 floating point. log2(a * 2^b) = log2(a) + b. This makes it easier to write your log2 function: You don't need to have it be accurate for every positive number, just on the interval [1, 2). Similarly, to calculate 2^x, you can multiply 2^(integer part of x) * 2^(fractional part of x). The first part is trivial to store in a floating point number, for the second part, you just need a 2^x function over the interval [0, 1).

The hard part is finding a good approximation of 2^x and log2(x). A simple approach is to use Taylor series.

answered 2010-05-23T18:05:49.840

Your Answer