computing powers by repeated squaring

From time to time, there arise occasions where one wants to raise a number to a large integer power. While one can compute xn by multiplying x by itself n times, not only does this entail a large expenditure of effort when n is large, but roundoff errors can accumulate. A more efficient approach is to first rise x to powers of two by successive squaring, then multiply to obtain xn. This procedure will now be explained by computing 1.08145187.

The first step is to express n as a sum of powers of two, i.e. in base 2. In our example, we have 187=1+2+8+16+32+128.

By the basic properties of exponentiation, we therefore have x187=xx2x8x16x32x128.

The next step is to raise 1.08145 to powers of two, which we accomplish by repeatedly squaring like so: (In order to guard against roundoff error, we work with more decimal places than needed and round off at the end of the computation.)

x =1.08145
x2 =1.1695341
x4 =(x2)2=1.16953412=1.3678100
x8 =(x4)2=1.36781002=1.8709042
x16 =(x8)2=1.87090422=3.5002825
x32 =(x16)2=3.50028252=12.251978
x64 =(x32)2=12.2519782=150.110965
x128 =(x64)2=150.1109652=26523642.95

Finally, we multiply together the appropriate powers to obtain our answer:


Hence, we compute 1.08145187=2.69162×109.

Note that this computation involved only 12 multiplications as opposed to 186 multiplications. More generally, we will require log2n repeated squarings and up to log2n multiplications of the repeated squares, or a total of between log2n and 2log2n multiplications to compute xn this way.

More generally, the same method can be used to compute xn when x is a complex number or a matrix, or something even more general, such as an element of a group. Thus this approach can be adapted to computing exponentialsMathworldPlanetmathPlanetmath and trigonometric functionsDlmfMathworld, numerical approximation of differential equationMathworldPlanetmath, and the like.

Title computing powers by repeated squaring
Canonical name ComputingPowersByRepeatedSquaring
Date of creation 2013-03-22 19:18:45
Last modified on 2013-03-22 19:18:45
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 8
Author rspuzio (6075)
Entry type AlgorithmMathworldPlanetmath
Classification msc 65B99