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)
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
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
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.
Related:
For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.
10 comments:
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
Btw, "halving" on 1st paragraph. Misspelling already for the blog hits? :P
mwm,
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. :)
Ahh :P ..my 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.
hmmnnn...the fast-multiply is just like having a code of x*y in short...
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.
My solution is even simpler:
(define (* a b)
(cond ((= b 0) 0)
((even? b) (* (double a) (halve b)))
(else (+ a (* a (- b 1))))))
Your solution requires Θ(n) space. There is solution that requires Θ(1) space:
1 #lang scheme
2
3 (define (double x) (+ x x))
4 (define (halve x) (/ x 2))
5
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)))))
10
11 (display (mul 2 10 0))
12 (newline)
13
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))))))
Post a Comment