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 by multiplying by itself times, not only does this entail a large expenditure of effort when is large, but roundoff errors can accumulate. A more efficient approach is to first rise to powers of two by successive squaring, then multiply to obtain . This procedure will now be explained by computing .
The first step is to express as a sum of powers of two, i.e. in base 2. In our example, we have .
By the basic properties of exponentiation, we therefore have .
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.)
Finally, we multiply together the appropriate powers to obtain our answer:
Hence, we compute .
Note that this computation involved only 12 multiplications as opposed to 186 multiplications. More generally, we will require repeated squarings and up to multiplications of the repeated squares, or a total of between and multiplications to compute this way.
More generally, the same method can be used to compute when 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|
|Date of creation||2013-03-22 19:18:45|
|Last modified on||2013-03-22 19:18:45|
|Last modified by||rspuzio (6075)|