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.

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	Algorithm
Classification	msc 65B99