ALAN@AI.AI.MIT.EDU (Alan Bawden) (06/10/89)
; This code assumes -perfect- arithmetic, so it wont get the
; exactness correct in any particular implementation.
; To really understand how this works, you should go learn about continued
; fractions.
(define (rationalize x e)
(simplest-rational (- x e) (+ x e)))
; Produces the simplest rational between X and Y inclusive.
; (In the comments that follow, [x] means floor(x).)
(define (simplest-rational x y)
(define (simplest-rational-internal x y) ; assumes 0 < X < Y
(let ((fx (floor x)) ; [X] <= X < [X]+1
(fy (floor y))) ; [Y] <= Y < [Y]+1, also [X] <= [Y]
(cond ((not (< fx x))
;; X is an integer so X is the answer:
fx)
((= fx fy)
;; [Y] = [X] < X < Y so expand the next term in the continued
;; fraction:
(+ fx (/ (simplest-rational-internal (/ (- y fy)) (/ (- x fx))))))
(else
;; [X] < X < [X]+1 <= [Y] <= Y so [X]+1 is the answer:
(+ 1 fx)))))
(cond ((< y x)
;; Y < X so swap and try again:
(simplest-rational y x))
((not (< x y))
;; X = Y so if that is a rational that is the answer, otherwise
;; there is nothing we can return at all.
(if (rational? x) x (error)))
((positive? x)
;; 0 < X < Y which is what SIMPLEST-RATIONAL-INTERNAL expects:
(simplest-rational-internal x y))
((negative? y)
;; X < Y < 0 so 0 < -Y < -X and we negate the answer:
(- (simplest-rational-internal (- y) (- x))))
(else
;; X <= 0 <= Y so zero is the answer:
0)))