Consider the problem of computing the exponential of a given number. We would like a procedure 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{array}{lll} b^{n} &=& b\cdot b^{n-1}\\ b^{0} &=& 1 \end{array} \] which translates readily into the procedure function

Original	JavaScript
(define (expt b n) (if (= n 0) 1 (* b (expt b (- n 1)))))	function expt(b, n) { return 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:

Original	JavaScript
(define (expt b n) (expt-iter b n 1)) (define (expt-iter b counter product) (if (= counter 0) product (expt-iter b (- counter 1) (* b product))))	function expt(b, n) { return expt_iter(b, n, 1); } function expt_iter(b, counter, product) { return counter === 0 ? product : expt_iter(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 \[ \begin{array}{l} b\cdot(b\cdot(b\cdot(b\cdot(b\cdot(b\cdot(b\cdot b)))))) \end{array} \] we can compute it using three multiplications: \[ \begin{array}{lll} b^{2} &= & b\cdot b\\ b^{4} &= & b^{2}\cdot b^{2}\\ b^{8} &= & b^{4}\cdot b^{4} \end{array} \]

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{array}{llll} b^{n} &=& (b^{n/2})^{2} &\qquad\,\mbox{if}\ n\ \mbox{is even}\\ b^{n} &=& b\cdot b^{n-1} &\qquad\mbox{if}\ n\ \mbox{is odd} \end{array} \] We can express this method as a procedure: function:

Original	JavaScript
(define (fast-expt b n) (cond ((= n 0) 1) ((even? n) (square (fast-expt b (/ n 2)))) (else (* b (fast-expt b (- n 1))))))	function fast_expt(b, n) { return n === 0 ? 1 : is_even(n) ? square(fast_expt(b, n / 2)) : b * fast_expt(b, n - 1); }

where the predicate to test whether an integer is even is defined in terms of the primitive procedure remainder, operator %, which computes the remainder after integer division, by

Original	JavaScript
(define (even? n) (= (remainder n 2) 0))	function is_even(n) { return n % 2 === 0; }

The process evolved by fast-expt fast_expt grows logarithmically with $n$ in both space and number of steps. To see this, observe that computing $b^{2n}$ using fast-expt 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.[1]

The difference between $\Theta(\log n)$ growth and $\Theta(n)$ growth becomes striking as $n$ becomes large. For example, fast-expt fast_expt for $n=1000$ requires only 14 multiplications.[2] 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.[3]

Exercise 1.16 Design a procedure function that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt. fast_expt. (Hint: Using the observation that $(b^{n/2})^2 =(b^2)^{n/2}$, keep, along with the exponent $n$ and the base $b$, an additional state variable $a$, and define the state transformation in such a way that the product $a b^n$ is unchanged from state to state. At the beginning of the process $a$ is taken to be 1, and the answer is given by the value of $a$ at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

Solution

function fast_expt_iter(a, b, n){ return n === 0 ? a : is_even(n) ? fast_expt_iter(a, b * b, n / 2) : fast_expt_iter(a * b, b, n - 1); } function fast_expt(b, n){ return fast_expt_iter(1, b, n); }

Exercise 1.17 The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure function (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure: function:

Original	JavaScript
(define (* a b) (if (= b 0) 0 (+ a (* a (- b 1)))))	function times(a, b) { return b === 0 ? 0 : a + times(a, b - 1); }

This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operations the functions double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure function analogous to fast-expt fast_expt that uses a logarithmic number of steps.

Solution

Original	JavaScript
	function double(x) { return x + x; } function halve(x) { return x / 2; } function fast_times(a, b) { return b === 1 ? a : a === 0 || b === 0 ? 0 : is_even(b) ? double(fast_times(a, halve(b))) : a + fast_times(a, b - 1); }

Exercise 1.18 Using the results of exercises 1.16 and 1.17, devise a procedure function that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.[4]

Solution

Original	JavaScript
	function double(x) { return x + x; } function half(x) { return x / 2; } function fast_times_iter(total, a, b) { return b === 1 ? total + a : a === 0 || b===0 ? 0 : is_even(b) ? fast_times_iter(total, double(a), half(b)) : fast_times_iter(total + a, a, b - 1); } function times(a, b) { return fast_times_iter(0, a, b); }

Exercise 1.19 There is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps. Recall the transformation of the state variables $a$ and $b$ in the fib-iter fib_iter process of section 1.2.2: $a\leftarrow a+b$ and $b\leftarrow a$. Call this transformation $T$, and observe that applying $T$ over and over again $n$ times, starting with 1 and 0, produces the pair $\textrm{Fib}(n+1)$ and $\textrm{Fib}(n)$. In other words, the Fibonacci numbers are produced by applying $T^n$, the $n$th power of the transformation $T$, starting with the pair $(1,0)$. Now consider $T$ to be the special case of $p=0$ and $q=1$ in a family of transformations $T_{pq}$, where $T_{pq}$ transforms the pair $(a,b)$ according to $a\leftarrow bq+aq+ap$ and $b\leftarrow bp+aq$. Show that if we apply such a transformation $T_{pq}$ twice, the effect is the same as using a single transformation $T_{p'q'}$ of the same form, and compute $p'$ and $q'$ in terms of $p$ and $q$. This gives us an explicit way to square these transformations, and thus we can compute $T^n$ using successive squaring, as in the fast-expt fast_expt procedure. function. Put this all together to complete the following procedure, function, which runs in a logarithmic number of steps:[5]

Original	JavaScript
(define (fib n) (fib-iter 1 0 0 1 n)) (define (fib-iter a b p q count) (cond ((= count 0) b) ((even? count) (fib-iter a b ?? ; compute p' ?? ; compute q' (/ count 2))) (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))))	function fib(n) { return fib_iter(1, 0, 0, 1, n); } function fib_iter(a, b, p, q, count) { return count === 0 ? b : is_even(count) ? fib_iter(a, b, $\langle{}$??$\rangle$, // compute p' $\langle{}$??$\rangle$, // compute q' count / 2) : fib_iter(b * q + a * q + a * p, b * p + a * q, p, q, count - 1); }

Solution

Original	JavaScript
	function fib(n) { return fib_iter(1, 0, 0, 1, n); } function fib_iter(a, b, p, q, count) { return count === 0 ? b : is_even(count) ? fib_iter(a, b, p * p + q * q, 2 * p * q + q * q, count / 2) : fib_iter(b * q + a * q + a * p, b * p + a * q, p, q, count - 1); }