Thursday, September 23, 2010

SICP 2.1: Rational numbers

From SICP section 2.1.1 Example: Arithmetic Operations for Rational Numbers

Exercise 2.1 asks us to define a better version of make-rat that handles both positive and negative arguments. Here's the last version from the text, along with several example cases to show how it works:
(define (make-rat n d)
(let ((g (gcd n d)))
(cons (/ n g) (/ d g))))

> (define x (make-rat 1 2))
> (print-rat x)

1/2
> (define x (make-rat -1 -2))
> (print-rat x)

-1/-2
> (define x (make-rat 1 -2))
> (print-rat x)

1/-2
> (define x (make-rat -1 2))
> (print-rat x)

-1/2

The new version of make-rat should normalize the sign so that if the resulting rational number is positive, both the numerator and denominator are positive. If the rational number is negative, only the numerator should be negative.

We can correct make-rat by checking to see if the denominator is negative. If it is, we need to multiply both the numerator and denominator by -1 to normalize the result. If not, we just pass the arguments bare to cons.
(define (make-rat n d)
(let ((g (gcd n d)))
(if (< d 0)
(cons (/ (* n -1) g) (/ (* d -1) g))
(cons (/ n g) (/ d g)))))

We can use the same definitions as before to see the results from the new make-rat procedure.
> (define x (make-rat 1 2))
> (print-rat x)

1/2
> (define x (make-rat -1 -2))
> (print-rat x)

1/2
> (define x (make-rat 1 -2))
> (print-rat x)

-1/2
> (define x (make-rat -1 2))
> (print-rat x)

-1/2


Related:

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

6 comments:

AMB said...

LISP is one thing I've always wanted to learn. I've seen you around on StackOverflow and noticed you committed to the game of go proposal, which I'd like to thank you for, because I just can't wait until it goes beta. Anyway, these posts about SICP are invaluable. I'll be coming back to visit.

Bill the Lizard said...

AMB,
I'm really looking forward to the Game of Go site too. I've gotten one other person to join, and he's really active in a Go club so I hope he'll bring others. I haven't played OTB in a couple of years now, so I really need all the help I can get. :)

Anonymous said...

I'm not really sure how this works for you, it doesn't work for me. The only thing I could think of is that your implementation of gcd is different than mine. I used the implementation from the book:

(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))

If we take the example of -1/-2 the result of gcd will be -1. After testing the sign of d in the if statement, d = -2 we multiply both parts by -1, then divide by the result of gcd -1, which will give us again -1/-2.

Thanks!

Bill the Lizard said...

Anonymous,

Just to clarify, I'm not using the implementation of gcd from the book, I'm using the one built in to Scheme.

> (gcd -1 -2)
1

Unknown said...

Bill, would it make sense to use the "negative?" function instead of (< d 0)? My thinking is the former function might be a more generic operation.

Anonymous said...

For reference, the book implementation returns negative because it's not totally right. The GCD is the greatest positive integer that divides both numerator and denominator.

Take -8 and 16,

The book GCD will step through like so

gcd -8 16
gcd 16 -8
gcd -8 0
-8

You can fix this in one of two ways. Either take the absolute value of a in GCD, or take the absolute value of the output of GCD in the function. Your choice.