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 n1 multiplications. Instead we could proceed as follows :

if n is even, say n =2k , then calculate x^{2}, and then raise that to the power k

if n is odd, say n=2k+1, then calculate x^{2}, and then raise that to the power k, then multiply by x.
You should probably also remember that x
^{1}=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
^{2})
^{4}
4 is even x
^{4}=(x
^{2})
^{2}
Hence x
^{9} = 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
polymorphicOf 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 builtin function that returns the product of a pair of integers).