Wednesday, January 13, 2010

SICP Exercise 1.17: Multiplication by repeated addition

From SICP section 1.2.4 Exponentiation

Exercise 1.17 asks us to design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps. We're told that in addition to adding, we can use procedures for doubling or halving an integer argument.
(define (double x)
(+ x x))

(define (halve x)
(/ x 2))

We'll also use the same even? procedure we've seen before:
(define (even? n)
(= (remainder n 2) 0))

The following multiplication procedure that takes a linear number of steps is given:
(define (* a b)
(if (= b 0)
(+ a (* a (- b 1)))))

This procedure defines multiplication in terms of the algorithm we all learned in grade school: add a to itself b times.

The exercise also makes reference to the following fast-expt procedure, which we can use as a guide:
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))

This procedure makes use of the following observations:

bn = (bn/2)2 if n is even
bn = b * bn-1 if n is odd

We can define similar rules for integer multiplication.

a * b = 2 * (a * b/2) if be is even
a * b = a + a * (b - 1) if b is odd

The first rule tells us when to use our procedures double and halve. The second rule just lets us take an odd b and make it even in preparation for the next iteration. Translating these rule into a Scheme procedure give us:
(define (fast-mult a b)
(cond ((= b 0) 0)
((= b 1) a)
((even? b) (double (fast-mult a (halve b))))
(else (+ a (fast-mult a (- b 1))))))

The procedure takes a logarithmic number of steps. If you double the size of the input parameter b, the procedure takes only one more step to compute the product.


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


mwm said...

I challenge you to make procedures only with "+1", "-1" and "zero?" procedures already made, that adds 1, subs 1 and checks if it's zero to any number, respectively.

Make "sum", "sub" "mult" and "div".
That was my "Programming Fundamentals" course first exercises on Scheme :P

mwm said...

Btw, "halving" on 1st paragraph. Misspelling already for the blog hits? :P

Bill the Lizard said...

Those are great warm-up exercises. I love problems that make you re-implement familiar operations in ways you might not have thought about before (at least not for some time). They're great for students because the problem is well understood, so they can focus on the solution.

I'm pretty sure "halving" is the right spelling for the word meaning "to divide in half." It's not getting picked up by my spell checker, at least. Anyway, at least it got you to comment. :)

mwm said...

Ahh :P bad then. Not that much of an expert in English. Portuguese here :) Yeah, halving surely exists. Just automatically wanted that to be a misspelled word as an internet blog (flame) reader :P

Keep up the good work.

Anonymous said...

hmmnnn...the fast-multiply is just like having a code of x*y in short...

alinrus said...

one could even go as far as checking which of the two numbers is smaller and use that as the iterator. it's a nice optimization.

mgr said...

My solution is even simpler:

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

Iain said...
This comment has been removed by the author.
lpaul7 said...

Your solution requires Θ(n) space. There is solution that requires Θ(1) space:

1 #lang scheme
3 (define (double x) (+ x x))
4 (define (halve x) (/ x 2))
6 (define (mul a b p)
7 (cond ((= b 0) p)
8 ((even? b) (mul a (halve b) (+ b p)))
9 (else (mul a (- b 1) (+ a p)))))
11 (display (mul 2 10 0))
12 (newline)

Splanky222 said...

Here's a different sort of flavor I did just for kicks. If both a and b are even, then ab = 4*(a/2)(b/2).Together with the identities:
ab = a + a(b-1) = b + (a-1)b = a + b -1 + (a-1)(b-1)
you can do
(define (mult a b)
(cond ((= 1 a) b)
((= 1 b) a)
((even? a) (if (even? b)
(double (double (mult (halve a) (halve b))))
(+ a (mult a (- b 1)))))
((even? b) (+ b (mult (- a 1) b)))
(else (+ a b (- 1) (mult (- a 1) (- b 1))))))