Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!bloom-beacon!AI.AI.MIT.EDU!ALAN
From: ALAN@AI.AI.MIT.EDU (Alan Bawden)
Newsgroups: comp.lang.scheme
Subject: Algorithm for RATIONALIZE
Message-ID: <607195.890609.ALAN@AI.AI.MIT.EDU>
Date: 9 Jun 89 20:38:12 GMT
Sender: daemon@bloom-beacon.MIT.EDU
Organization: The Internet
Lines: 40

; 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)))