Exercise 1.18 asks us to use the results from the two previous exercises (1.16 and 1.17) to devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling and halving, and which uses a logarithmic number of steps.
The key idea from exercise 1.16 was to keep an additional state variable
a, and manipulate the state transition so that the product (a * bn) remained unchanged. We can modify our solution to exercise 1.17 to use the same idea. Since we're now dealing with multiplication instead of exponentiation, the invariant quantity will be (a * b + p) where
bare the two operands, and
pwill be our state variable. Initially
pwill be 0, but by the end of the iterative process it will hold the product (a * b).
(define (even? n)
(= (remainder n 2) 0))
(define (double x)
(+ x x))
(define (halve x)
(/ x 2))
(define (mult-iter a b p)
(cond ((= 0 b) p)
((even? b) (mult-iter (double a) (halve b) p))
(else (mult-iter a (- b 1) (+ a p)))))
(define (mult a b)
(mult-iter a b 0))
For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.