How do you efficiently compute an for integer n? You could multiply a*a*a*…*a, n-1 multiplications, but there are much more efficient ways. For example, a8 could be computed by ((a2)2)2 in three multiplications. This example suggests it may be worthwhile to think about the binary representation of the exponent.
Here’s an algorithm. Write the exponent n in binary. Read the binary representation from left to right, starting with the second bit from the left. Start with the number a, and every time you read a 0 bit, square what you’ve got. Every time you read a 1 bit, square what you’ve got and multiply by a. It follows that an can be computed using no more than 2 log2(n) multiplications.
As an example, suppose we want to calculate 713. In binary, 13 is written as 1101. We skip over the leading 1 then read 1, 0, and 1. So we calculate ((((72)7)2)2)7. In C notation, we would compute as follows.
x = 7; x *= x; x *= 7; x *= x; x *= x; x *= 7;
In number theory calculations, such as arise in cryptography, it’s often necessary to compute an (mod m) for very large integers a, n, and m. These numbers may be hundreds or thousands of digits long and so of course the calculations cannot be carried out using ordinary machine integers. You could compute an first then reduce the result (mod m), but it would be more efficient to reduce (mod m) after every multiplication. This puts an upper bound on the size of numbers (and hence the amount of memory) needed for the calculation.
The same algorithm works when a is not an integer but a matrix. For example, consider a large matrix M that gives the connections between nodes in a graph. M contains a 1 in position (i, j) if the ith and jth nodes are connected by an edge and contains a 0 otherwise. The nth power of M tells which nodes are connected by paths of length less than or equal to n. If M is large, we don’t want to do unnecessary multiplications in computing Mn.
For some exponents, the method given above can be improved. The smallest exponent for which you can improve on the binary algorithm is 15. Using the binary algorithm, computing a15 requires six multiplications. But you could compute the same quantity in five multiplications as follows.
b = a*a*a; c = b*b; c *= c; c *= b;
For more examples, see Seminumerical Algorithms section 4.6.3.