Monday, 26 March 2007

Interesting Solutions to SICP Chapter 1

I have started working through SICP chapter 1, using the Dr Scheme interactive environment. I will post my more interesting solutions and comments.

Ken Dyck gives a more complete solution set.

Comment: Rather than finding the larger two explicitly, I find the smallest and use a simple mathematical identity.

My solutions:

Exercise 1.3. Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.

(define (f a b c)
(define (lt a b) (if (> a b) b a))
(define (least a b c) (lt a (lt b c)))
(define (square x) (* x x))

(+ (square a)
(square b)
(square c)
(- (square (least a b c)))))
Comment: Rather than finding the larger two explicitly, I find the smallest and use a simple mathematical identity.

Exercises 1.17 & 1.18: Devise recursive and iterative algorithms for multiplication that take a logarithmic number of steps.
(define (mul-recursive a b)
(cond ((= b 0) 0)
((even? b) (mul-recursive (double a) (halve b)))
(else (+ a (mul-recursive a (- b 1))))))

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

(mul-iterative 0 a b))
Comments: Observe how similar the two solutions are. The iterative solution is especially easy to follow if you expand out an example.

3 comments:

Ken Dyck said...

Clever! I would never have thought of solving it that way.

Thanks for sharing your solution.

Daniel Prager said...

Thanks Ken.

(Perils of a mathematical education.)

And thank-you for making your solutions available online!

veselov said...

I've also started to share my solutions, together with my friends. We've created SICP wiki, which can be found here:

http://sicp.org.ua

Solutions in Scheme, Haskell and Oberon are available, as long as its discussions and comments.