Structure and Interpretation of Computer Programs

This is a linear recursive process, which requires   (n) steps and   (n) space. Just as with factorial, we

can readily formulate an equivalent linear iteration:

(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   (n) steps and   (1) 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:

(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 

remainder

 by 

(define (even? n)

  (= (remainder n 2) 0))

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   (

log

 n) growth.

37

---

The difference between   (

log

 n) growth and   (n) 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 (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 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 (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 1.18.  Using the results of exercises 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: a 

 a + b and b 

 a. 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 nth 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 

 bq + aq + ap and b 

 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

procedure. Put this all together to complete the following procedure, which runs in a logarithmic

number of steps:

41

(define (fib n)

  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)

  (cond ((= count 0) b)

        ((even? count)

---