Structure and Interpretation of Computer Programs

Exponentiation

Consider the problem of computing the exponential of a given number. We would like a function that takes as arguments a base \(b\) and a positive integer exponent \(n\) and computes \(b^n\). One way to do this is via the recursive definition

\[ \begin{align} & b^n = b \cdot b^{n-1} \\ & b^0 = 1 \end{align} \]

which translates readily into the function

(defun expt (b n)
  (if (== n 0)
      1
      (* b (expt b (- n 1)))))

This is a linear recursive process, which requires \(\Theta(n)\) steps and \(\Theta(n)\) space. Just as with factorial, we can readily formulate an equivalent linear iteration:

(defun expt (b n)
  (expt b n 1))

(defun expt (b counter product)
  (if (== counter 0)
      product
      (expt b
            (- counter 1)
            (* b product))))

This version requires \(\Theta(n)\) steps and \(\Theta(1)\) space.

We can compute exponentials in fewer steps by using successive squaring. For instance, rather than computing \(b^8\) as

\[ b \cdot (b \cdot (b \cdot (b \cdot (b \cdot (b \cdot (b \cdot b)))))) \]

we can compute it using three multiplications:

\[ \begin{align} & b^2 = b \cdot b \\ & b^4 = b^2 \cdot b^2 \\ & b^8 = b^4 \cdot b^4 \\ \end{align} \]

This method works fine for exponents that are powers of 2. We can also take advantage of successive squaring in computing exponentials in general if we use the rule

\[ \begin{align} & b^n = (b^\frac{n}{2})^2 & \mbox{if } n \ \text{is even} \\ & b^n = b \cdot b^{n-1} & \mbox{if } n \ \text{is odd} \\ \end{align} \]

We can express this method as a function:

(defun fast-expt (b n)
  (cond ((== n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        ('true (* b (fast-expt b (- n 1))))))

where the predicate to test whether an integer is even is defined in terms of the primitive function rem by

(defun even? (n)
  (=:= 0 (rem (trunc n) 2)))

The process evolved by fast-expt grows logarithmically with \(n\) in both space and number of steps. To see this, observe that computing \(b^{2n}\) using fast-expt requires only one more multiplication than computing \(b^n\). The size of the exponent we can compute therefore doubles (approximately) with every new multiplication we are allowed. Thus, the number of multiplications required for an exponent of n grows about as fast as the logarithm of \(n\) to the base 2. The process has \(\Theta(\log n)\) growth.¹

The difference between \(\Theta(\log n)\) growth and \(\Theta(n)\) growth becomes striking as \(n\) becomes large. For example, fast-expt for \(n = 1000\) requires only 14 multiplications.² It is also possible to use the idea of successive squaring to devise an iterative algorithm that computes exponentials with a logarithmic number of steps (see exercise 1.16), although, as is often the case with iterative algorithms, this is not written down so straightforwardly as the recursive algorithm.³