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 xy 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.

[edit] Example

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

31 3
32 9 = 3 \times 3
34 81 = 9 \times 9
38 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

[edit] Analysis

[edit] 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 )
      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(lgy) 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}.

Personal tools