SICP Exercise 1.18: Iterative Multiplication

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.

To remind us, exercise 1.16 took a recursive implementation of fast-expt which utilized successive squaring:

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

...and produced a corresponding iterative implementation:

(define (fast-expt b n)
  (define (iter a b n)
    (cond ((= n 0) a)
          ((even? n) (iter a (square b) (/ n 2)))
          (else (iter (* a b) b (- n 1)))))
  (iter 1 b n))

To do this we introduced a state variable, a, and established the invariant quantity was abⁿ, where b was the base and n the exponent. For any operation we applied to n to bring us nearer to the terminating condition we had to apply an appropriate operation to either b or a in order to maintain the invariant.

Okay, so here's the result from exercise 1.17:

(define (mult a b)
  (cond ((= b 0) 0)
        ((even? b) (double (mult a (halve b))))
        (else (+ a (mult a (- b 1))))))

To produce a corresponding iterative implementation, we're going to have to follow a similar set of steps. We introduce a state variable, s, that we will use for accumulating the result into, and then establish the invariant quantity s + ab, where a and b correspond to the numbers to be multiplied. So in what ways can we maintain the invariant quantity s + ab while changing at least one of s, a and b? Well, we can double a if we half b. We can also add a to s if we subtract 1 from b. I.e.

• s + ab = s + 2a(b/2)
• s + ab = (s + a) + a(b - 1)

The first of these relationships give us a way to maintain the invariant quantity when b is even while the second gives us a way to maintain it when b is odd. So, in the same way we used the invariant quantity relationships determined in exercise 1.16 to produce the iterative implementation from the recursive one, we can produce:

(define (mult a b)
  (define (iter s a b)
    (cond ((= b 0) s)
          ((even? b) (iter s (double a) (halve b)))
          (else (iter (+ a s) a (- b 1)))))
  (iter 0 a b))

...and try it out:

> (mult 2 4)
8
> (mult 4 2)
8
> (mult 3 21)
63
> (mult 12 34)
408