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.³