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

This is a linear recursive process, which requires(define (expt b n) (if (= n 0) 1 ( b (expt b (- n 1)))))

(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))))

This version requires _{} steps and
_{} space.

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:

where the predicate to test whether an integer is even is defined in terms of the primitive 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))))))

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

The difference between _{} growth and
_{} growth becomes striking as *n*
becomes large. For example, ` fast-expt` for *n = 1000*
requires only 14 multiplications.^{38} 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. ^{39}

**Exercise 1.16**

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
_{}, 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 *ab ^{n}* is unchanged from state to state. At
the beginning of the process,

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

This algorithm takes a number of steps that is linear in(define ( a b) (if (= b 0) 0 (+ a ( a (- b 1)))))

**Exercise 1.18**

Using the results of 1.16 and 1.17, 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. ^{40}

**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` process of
section 1.2.2: x. Call this transformation
*T*, and observe that applying *T* over and over again
*n* times, starting with 1 and 0, produces the pair
Fib(*n*+ 1) and Fib(*n*). In other words, the Fibonacci
numbers are produced by applying *T ^{n}*, the

(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 (/ count 2))) (else (fib-iter (+ ( b q) ( a q) ( a p)) (+ ( b p) ( a q)) p q (- count 1)))))