SICP Exercise 1.18: Iterative multiplication

From SICP section 1.2.4 Exponentiation

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 * bⁿ) 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 a and b are the two operands, and p will be our state variable. Initially p will 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))

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.