Ames Laboratory, Department of Energy, ISU, Ames, Iowa

Integer Powers of a Number

An example of an algorithm optimization discussed in Knuth [10] is that of raising a number to an integer power by repeated multiplications. By saving and reusing partial products, the number of multiplications to compute aⁿ is usually much less than the n - 1 multiplications that would be done by a simple loop. For example, a¹⁵ can be computed with five multiplications using

a² = a a
a⁴ = a² a²
a⁵ = a⁴ a
a¹⁰ = a⁵ a⁵
a¹⁵ = a¹⁰ a⁵

Even this simple problem illustrates that minimizing operations results in 'tricks', i.e., methods that do not seem derivable by straightforward stepwise thinking. A straightforward method might be to express the exponent as a binary number, and compute products corresponding to every '1' in that number. For example,

a¹⁵ = a^1+2+4+8,
so a² = a a
a⁴ = a² a²
a⁸ = a⁴ a⁴
a¹² = a⁸ a⁴
a¹⁴ = a¹² a²
a¹⁵ = a¹⁴ a

Since this method uses six multiplications, it is inferior to the 'clever' method of more subtle derivation.

A further complication is that divide operations can sometimes reduce the work to get to a power, depending on the relative cost of multiplications and divides (and on the cost of handling divisions by zero). For instance, a³¹ can be computed by repeated squaring to get a³², and then dividing by a to get a³¹. The five multiplications and one division required will be faster than the seven operations needed using multiplications alone, if there is no cost for the a = 0 exception and division takes less time than 2 multiplications.

The optimization program of Section 4 easily generates optimal algorithms for the first powers of a number up to an exponent of 100. We simplified the program to consider only one initial input, a, and used the mathematical equivalence of the ring formed by multiplication and exponentiation to the ring formed by addition and multiplication. That is, the goal expression of 15a using only addition and subtraction is equivalent to a goal expression of a¹⁵ using only multiplication and division.

To automate the discovery of minimal operation counts, the algorithm was surrounded by the following control structure, where m(n) is the number of operations to find aⁿ:

 
n = 2

While n  nmax

     

     While  Search( mtest) fails

	Increment  mtest.

     End While

     Record method with  mtest operations.

     Increment n.

End While

An nCUBE 2 with 64 processors took 1.5 minutes to find all of the optimal methods tabled in Knuth, assuming no divisions. Divisions were then introduced with various weightings, since division takes longer than multiplication on most 1992 computers, by amounts that vary from computer to computer. The optimal sequence of operations with no divisions is shown in Figure 8 and with a division weighted the same as a multiplication is shown in Figure 9. The sequence of optimal operations when a division is weighted as two or more multiplications is the same as that with no divisions, for integer powers less than or equal to 100.

FIGURE 8: Power tree with multiplications.

FIGURE 9: Power tree with divisions weighed the same as multiplications.

Note that division is much less help than one might think. Given the high cost of division on many machines, plus the cost of exception handling when a = 0, the use of multiplications alone appears very attractive for low integer powers. For integer powers higher than 200 or so, other methods such as those given in [6] become advantageous.