Thursday, January 14, 2010

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 * 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 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))


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


thelsdj said...

It was nice that after some of the last few exercises requiring a lot of math / proof stuff. I was able to do this one and the previous myself, just looked here to check my work.

Kamagra said...

This is very great thing you have shared with us. Now I found enough resources by your tips about this issue, Thank you.

Anonymous said...

Thanks for posting all these -- they've been super helpful in getting me on the right track with SICP!

With that said, though, I don't think your above algorithm is correct. Right now p will be equal to the original a iff the multiplier " b " is odd, else p = 0. You can return a + p from mult-iter to fix this.

Bill the Lizard said...


If b is even, then the recursive call

(mult-iter (double a) (halve b) p)

is made. If the resulting value of (halve b) in this call ends up being odd, then a + p is what is used in the next recursive call in the else branch.

Step through a few test cases with odd and even values for b and I think you'll see what I mean.

Naeblis said...

These exercises are great, but I sometimes get the else part (when b is odd) wrong. Realized that I was initializing the state variable as 1, not 0. Here's the solution I implemented (I handle the case when b = 1 separately)

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

Anonymous said...

@Naeblis : I think the expression in else is wrong; the third argument should be (+ n a), so that the result is 'accumulated' correctly.

Anonymous said...

Thanks for all your work on these exercises. I've finally understood the concept of invariance in this context, that:

(a*b + p) = (2a * .5b +p) = (a*(b-1) + (p+a))

Thank you so much for sharing!

Anonymous said...

Hi Bill

For both the iterative and recursive case, can we define the order of growth in number of steps as log b to the base a ?