Repeated Squaring

From Algorithmist
Jump to: navigation, search

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[edit]

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[edit]

Pseudo-code[edit]

// 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}}}.