# Power function - different ways to compute powers

**mathguy**Dec 14, 2018 6:55 PM

While working on "Implementing Polynomials", and specifically in regards to the task of evaluating a polynomial at a given point (such as, at x = 1.0013), the issue of computing powers of numbers comes up naturally. In this branch I would like to discuss power functions specifically.

If n is a positive integer and x is a real number, we all know what x^n means, and how to compute it. In pseudo-code, something like this:

y := 1;

for i in 1..n loop

y := y * x;

end loop;

return y;

Oracle offers the function POWER(x, n) for this task; and, as in higher math, Oracle does not restrict the function to n being an INTEGER; it may be any real number, but x must be strictly positive.

So, what are some of the ways to compute powers, both for n integer and for n non-integer? How does Oracle implement it? (WHO KNOWS?) And are there any techniques to compute several different (integer) powers of the same number x in parallel, to save time, so that the evaluation of a POLYnomial can be optimized?

One way to express (and perhaps compute) POWER(x, n) when x and n are real numbers with x > 0 is as EXP( n * LN(x)). EXP can be calculated pretty fast (its Taylor series converges very quickly). I don't know how computers calculate LN - most likely not from its Taylor series, which converges very slowly. (There are several faster ways, I just don't know what is written in the C libraries or whatever Oracle, say, uses for LN).

For use with polynomials specifically, let's limit the discussion to n being a non-negative integer. Here is a way to compute powers (with n a non-negative integer) that are faster than the naive approach I showed at the top of this post.

We want to compute x^n, given x and n. Decompose n as a sum of powers of 2. For example, say we must compute x^53. Write 53 = 32 + 16 +4 + 1. x^53 = x^32 * x^16 * x^4 * x^1. We can compute successively x^2, x^4, x^8, x^16, x^32 (by squaring the previous result at each step) - this requires five multiplications. Always <= LOG(2, n). And then we need three more multiplications to get x^53; this is one less than the number of set bits in the binary representation of n. In any case, also always <= LOG(2, n). So, this approach will perform no more than 2 * LOG(2, n) multiplications, instead of n-1 multiplications as in the naive approach.

Here is a pseudo-code implementation:

y := 1;

z := x;

k := n;

while k > 1 loop

if mod(k, 2) = 1 then

y := y * z;

end if;

z := z * z;

k := trunc(k/2);

end loop;

y := y * z;

return y;

This should be even better in something like C: the exponent n is already a binary integer; at each step we check whether the right-most bit is set, and then we shift one bit to the right. No need for expensive function calls like MOD(k, 2) and TRUNC(k/2).

(I assume all of this is very well known to anyone with formal IT training; I am certain I am reinventing the wheel here...)

There is no such simplification if n is NOT an integer, by the way. Curiously, though, whatever Oracle uses, my tests show that there is no difference in execution time between POWER(1.000001, 800000) and POWER(1.000001, 800000.25). I found this very surprising; I expected the former to go much faster than the latter. I should be able to test the same in C to see if my expectation was wrong...

In any case, back to what's available in PL/SQL, and polynomial evaluation. The idea would be to consider the binary representation of ALL exponents with non-zero coefficient in a polynomial, and to compute all the needed powers of x at the same time. I'll try my hand at implementing polynomials as nested tables of monomials (or perhaps as associative arrays - I'll see if one may work better than the other) and apply this idea to evaluating a polynomial at a point, but I thought I'd put this out both for critique and to encourage others to work on it as well, if interested.