Fast Exponentiation is a more efficient way of raising an object (number, matrix, polynomial etc...) to a given power.
The first way we might try to raise an object x to the power n might be to calculate x*x*x ...*x.
Obviously we will get the right answer, but we are performing n-1 multiplications. Instead we could proceed as follows :
if n is even, say n =2k , then calculate x2, and then raise that to the power k
if n is odd, say n=2k+1, then calculate x2, and then raise that to the power k, then multiply by x.
You should probably also remember that x1
Informally we are cutting the problem in half each time, this divide and conquer
approach will give us O(log n) multiplications. For the sceptical
and for those who the previous sentence was total gibberish
, here's an example:
If we try to raise x to the power 9 the ordinary way, we calculate x*x*x*x*x*x*x*x*x, that's 8 multiplications.
Using this method, we have :
9 is odd, we need x * (x2
4 is even x4
= x * ((x^2)^2)^2
Each squaring is one multiplication, so we've only used 4 multiplications. But I can hear people shouting "So what you saved 4 mingy little multiplications
, I have a 2 Ghz PC
on my desktop ?!". To which I would reply that sometimes we are dealing with objects where multiplication is an expensive operation
, for example 1024x1024 matrices
, polynomials or even very large integers in an arbitrary precision arithmetic
system. And of course the savings are much larger if you are raising things to a bigger power.
Finally, some real code to do this. For the sake of obscurity, I'm going to write this in ML
fun power f x 1 =x
| power f x n = if (n mod 2=0) then power f(f (x,x)) (n div 2)
else f (x, power f (f (x,x)) (n div 2));
As you can see, this version will only work if n is greater or equal to 1 (ML
will guess that n has to be an integer
). In case you were wondering, f is the function to use to multiply 2 objects, making this function nice and polymorphic
Of course you can make this tail recursive (or iterative), by adding an accumulating argument, making it even more efficient, like so
fun power f x y 1 =f (x,y)
| power f x y n = if (n mod 2=0) then power f (f (x,x)) y (n div 2)
else power f (f (x,x)) (f (x,y)) (n div 2);
This function needs to be called initially with y set to one, so for example to calculate 2 15
, you would evaluate
power op* 2 1 15; (op* is a built-in function that returns the product of a pair of integers).