11-3 Integer Exponentiation

Computing xn by Binary Decomposition of n

A well-known technique for computing xn, when n is a nonnegative integer, involves the binary representation of n. The technique applies to the evaluation of an expression of the form x ?x ?x ?x ???x where ?is any associative operation, such as addition, multiplication including matrix multiplication, and string concatenation (as suggested by the notation ('ab')3 = 'ababab'). As an example, suppose we wish to compute y = x13. Because 13 expressed in binary is 1101 (that is, 13 = 8 + 4 + 1),



Thus, x13 may be computed as follows:



This requires five multiplications, considerably fewer than the 12 that would be required by repeated multiplication by x.

If the exponent is a variable, known to be a nonnegative integer, the technique can be employed in a subroutine, as shown in Figure 11-6.

Figure 11-6 Computing xn by binary decomposition of n.
int iexp(int x, unsigned n) {
牋 int p, y; 
牋 y = 1;牋牋牋牋牋牋牋牋牋牋 // Initialize result 
牋爌 = x;牋 牋牋牋牋牋牋牋牋牋// and p. 
牋爓hile(1) {
牋牋?if (n & 1) y = p*y;牋牋 // If n is odd, mult by p. 
牋牋牋n = n >> 1;牋牋牋牋牋牋 // Position next bit of n. 
牋牋牋if (n == 0) return y;牋 // If no more bits in n. 
牋牋牋p = p*p;牋牋牋牋牋牋牋?// Power for next bit of n. 

The number of multiplications done by this method is, for exponent n 1,



This is not always the minimal number of multiplications. For example, for n = 27 the binary decomposition method computes



which requires seven multiplications. However, the scheme illustrated by



requires only six. The smallest number for which the binary decomposition method is not optimal is n =15 (hint: x15 = (x3)5).

Perhaps surprisingly, there is no known simple method that, for all n, finds an optimal sequence of multiplications to compute xn. The only known methods involve an extensive search. The problem is discussed at some length in [Knu2, sec. 4.6.3].

The binary decomposition method has a variant that scans the binary representation of the exponent in left-to-right order [Rib, 32], which is analogous to the left-to-right method of converting binary to decimal. Initialize the result y to 1, and scan the exponent from left to right. When a 0 is encountered, square y. When a 1 is encountered, square y and multiply it by x. This computes graphics/11icon36.gifas



It always requires the same number of (nontrivial) multiplications as the right-to-left method of Figure 11-6.

2n in Fortran

The IBM XL Fortran compiler takes the definition of this function to be



It is assumed that n and the result are interpreted as signed integers. The ANSI/ISO Fortran standard requires that the result be 0 if n < 0. The definition above for n 31 seems reasonable in that it is the correct result modulo 232, and it agrees with what repeated multiplication would give.

The standard way to compute 2n is to put the integer 1 in a register and shift it left n places. This does not satisfy the Fortran definition, because shift amounts are usually treated modulo 64 or modulo 32 (on a 32-bit machine), which gives incorrect results for large or negative shift amounts.

If your machine has number of leading zeros, pow2(n) may be computed in four instructions as follows [Shep]:



The shift right operations are "logical" (not sign-propagating), even though n is a signed quantity.

If the machine does not have the "nlz" instruction, its use above can be replaced with one of the x = 0 tests given in "Comparison Predicates" on page 21, changing the expression graphics/11icon40.gifA possibly better method is to realize that the predicate 0 x 31 is equivalent to graphics/11icon41.gifand then simplify the expression for graphics/11icon42.gifgiven in the cited section; it becomes ?span class=docemphbolditalic1>x & (x - 32). This gives a solution in five instructions (four if the machine has and not):