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.
8 comments:
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.
This is very great thing you have shared with us. Now I found enough resources by your tips about this issue, Thank you.
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.
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.
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))))
@Naeblis : I think the expression in else is wrong; the third argument should be (+ n a), so that the result is 'accumulated' correctly.
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!
=)
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 ?
Post a Comment