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

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

3^{4} | |

3^{8} |

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

## [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 ) 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 .