Repeated Squaring

Repeated squaring, or repeated doubling is an algorithm that computes integer powers of a number quickly. The general problem is to compute $x^{y}$ for an arbitrary integer y. The naive method, doing y multiplications of x, is very slow. It can be sped up by repeatedly squaring x until the current power of x exceeds y, and then collecting the "useful" powers.

Example

So, which powers of x are useful? Consider the concrete example of computing $3^{13}$ . The binary representation of 13 is ${(1101)}_{2}$ , so $8+4+1=13$ .

 $3^{1}$ $3$ $3^{2}$ $9=3\times 3$ $3^{4}$ $81=9\times 9$ $3^{8}$ $6561=81\times 81$ Notice that each result is the square of the previous result, and hence can be computed in one multiplication.

$3^{1}\times 3^{4}\times 3^{8}=3^{13}=1594323$ Analysis

Pseudo-code

// Calculates n to the p power, where p is a positive number.
func power( var n as integer, var p as integer )
if p = 0 return 1
if p = 1 return n
if p is odd
return n * power( n * n, (p-1) / 2 )
else
return power( n * n, p / 2 )
end func

It is not neccesary to keep all the powers of x in memory, only a product accumulator and the last power of x is neccesary.

Note that the algorithm does only $O(\lg y)$ multiplications, since it has to do no more than twice as many multiplcations as the number of bits representing y.

In general, we use the equation $x^{y}=(x^{y~{\rm {div}}~2})^{2}\cdot x^{y{\bmod {2}}}$ .