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^{n}) 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