Exponentiation

Consider the problem of computing the exponential of a given number.
We would like a procedure 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

which translates readily into the procedure

(define (expt b n) (if (= n 0) 1 (* b (expt b (- n 1)))))This is a linear recursive process, which requires steps and space. Just as with factorial, we can readily formulate an equivalent linear iteration:

(define (expt b n) (expt-iter b n 1))This version requires steps and space.(define (expt-iter b counter product) (if (= counter 0) product (expt-iter b (- counter 1) (* b product))))

We can compute exponentials in fewer steps by using successive
squaring. For instance, rather than computing *b*^{8} as

we can compute it using three multiplications:

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

We can express this method as a procedure:

(define (fast-expt b n) (cond ((= n 0) 1) ((even? n) (square (fast-expt b (/ n 2)))) (else (* b (fast-expt b (- n 1))))))where the predicate to test whether an integer is even is defined in terms of the primitive procedure

(define (even? n) (= (remainder n 2) 0))The process evolved by

The difference between
growth and
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 ), although, as is often
the case with iterative algorithms, this is not written down so
straightforwardly as the recursive algorithm.^{}

**Exercise.**
Design a procedure that evolves an iterative exponentiation process
that uses successive squaring and uses a logarithmic number of steps,
as does `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.)

**Exercise.** 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 (in which it is assumed that
our language can only add, not multiply) is analogous to the `
expt` procedure:

(define (* a b) (if (= b 0) 0 (+ a (* a (- b 1)))))

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

**Exercise.**
Using the results of exercises
and , devise a procedure that generates an iterative
process for multiplying two integers in terms of adding, doubling, and
halving and uses a logarithmic number of steps.^{}

**Exercise.**

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` process of
section :
and
.
Call this transformation *T*, and observe that applying *T* over
and over again *n* times, starting with 1 and 0, produces the pair
and
.
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
and
.
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`
procedure. Put this all together to complete the following procedure,
which runs in a logarithmic number of steps:^{}

(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 ??; computep' ??; computeq' (/ count 2))) (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))))