1.2.4 Exponentiation


which translates readily into the procedure

(define (expt b n)
  (if (= n 0)


(define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
      (expt-iter b
                (- counter 1)
                ( b product))))

This version requires steps and space.


we can compute it using three multiplications:


We can express this method as a procedure:

(define (fast-expt b n)
  (cond ((= n 0) 1)
        (else ( b (fast-expt b (- n 1))))))


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

(define ( a b)
  (if (= b 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


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 Tn, the nth power of the transformation T, starting with the pair (0,1). Now, consider T to be a special case of p= 0 and q = 1 in a family of transformations Tpq, where Tpq transforms the pair (a, b) according to . Show that if we apply such a transformation Tpq twice, the effect is the same as using a single transformation of the same form, and compute and of p and q. This gives us an explicit way to square these transformations, and thus we can compute Tn 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)
         (fib-iter a
                   (/ count 2)))
         (else (fib-iter (+ ( b q) ( a q) ( a p))
                         (+ ( b p) ( a q))
                         (- count 1)))))