Repeated Squaring

From Algorithmist
Jump to navigation Jump to search

Repeated squaring, or repeated doubling is an algorithm that computes integer powers of a number quickly. The general problem is to compute 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.


So, which powers of x are useful? Consider the concrete example of computing . The binary representation of 13 is , so .

Notice that each result is the square of the previous result, and hence can be computed in one multiplication.



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