## You are here

Homecomputing powers by repeated squaring

## Primary tabs

# 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 $x^{n}$ 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 $x^{n}$. This procedure will now be explained by computing $1.08145^{{187}}$.

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 $x^{{187}}=x\cdot x^{2}\cdot x^{8}\cdot x^{{16}}\cdot x^{{32}}\cdot x^{{128}}$.

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

$\displaystyle x$ | $\displaystyle=1.08145$ | ||

$\displaystyle x^{2}$ | $\displaystyle=1.1695341$ | ||

$\displaystyle x^{4}$ | $\displaystyle=(x^{2})^{2}=1.1695341^{2}=1.3678100$ | ||

$\displaystyle x^{8}$ | $\displaystyle=(x^{4})^{2}=1.3678100^{2}=1.8709042$ | ||

$\displaystyle x^{{16}}$ | $\displaystyle=(x^{8})^{2}=1.8709042^{2}=3.5002825$ | ||

$\displaystyle x^{{32}}$ | $\displaystyle=(x^{{16}})^{2}=3.5002825^{2}=12.251978$ | ||

$\displaystyle x^{{64}}$ | $\displaystyle=(x^{{32}})^{2}=12.251978^{2}=150.110965$ | ||

$\displaystyle x^{{128}}$ | $\displaystyle=(x^{{64}})^{2}=150.110965^{2}=26523642.95$ |

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

$1.08145\cdot 1.1695341\cdot 1.8709042\cdot 3.5002825\cdot 12.251978\cdot 26523% 642.95=2691617615$ |

Hence, we compute $1.08145^{{187}}=2.69162\times 10^{9}$.

Note that this computation involved only 12 multiplications as opposed to 186 multiplications. More generally, we will require $\log_{2}n$ repeated squarings and up to $\log_{2}n$ multiplications of the repeated squares, or a total of between $\log_{2}n$ and $2\log_{2}n$ multiplications to compute $x^{n}$ this way.

More generally, the same method can be used to compute $x^{n}$ 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 exponentials and trigonometric functions, numerical approximation of differential equation, and the like.

## Mathematics Subject Classification

65B99*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections