11-3 Integer Exponentiation

Computing xⁿ by Binary Decomposition of n

A well-known technique for computing xⁿ, 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')³ = 'ababab'). As an example, suppose we wish to compute y = x¹³. Because 13 expressed in binary is 1101 (that is, 13 = 8 + 4 + 1),

Thus, x¹³ 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 xⁿ by binary decomposition of n.

int iexp(int x, unsigned n) {
   int p, y; 
 
   y = 1;                     // Initialize result 
   p = x;                     // and p. 
   while(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: x¹⁵ = (x³)⁵).

Perhaps surprisingly, there is no known simple method that, for all n, finds an optimal sequence of multiplications to compute xⁿ. 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 as

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

2ⁿ 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 2³², and it agrees with what repeated multiplication would give.

The standard way to compute 2ⁿ 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 A possibly better method is to realize that the predicate 0 x 31 is equivalent to and then simplify the expression for given 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):