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.