fast exponentiation

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 x², and then raise that to the power k
• if n is odd, say n=2k+1, then calculate x², and then raise that to the power k, then multiply by x.

You should probably also remember that x¹=x
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 * (x²)⁴
4 is even x⁴=(x²)²
Hence x⁹ = 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 ¹⁵, you would evaluate
power op* 2 1 15; (op* is a built-in function that returns the product of a pair of integers).