# Repeated Squaring

Repeated squaring, or repeated doubling is an algorithm that computes integer powers of a number quickly. The general problem is to compute ${\displaystyle 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 ${\displaystyle 3^{13}}$. The binary representation of 13 is ${\displaystyle {(1101)}_{2}}$, so ${\displaystyle 8+4+1=13}$.

 ${\displaystyle 3^{1}}$ ${\displaystyle 3}$ ${\displaystyle 3^{2}}$ ${\displaystyle 9=3\times 3}$ ${\displaystyle 3^{4}}$ ${\displaystyle 81=9\times 9}$ ${\displaystyle 3^{8}}$ ${\displaystyle 6561=81\times 81}$

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

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle x^{y}=(x^{y~{\rm {div}}~2})^{2}\cdot x^{y{\bmod {2}}}}$.