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


Related:

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

7 comments:

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...

Anonymous,

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)
(cond
((= 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!
=)