[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: Scheme@MC.LCS.MIT.EDU*Subject*: Algorithm for RATIONALIZE*From*: Alan Bawden <ALAN%AI.AI.MIT.EDU@MINTAKA.LCS.MIT.EDU>*Date*: Fri ,9 Jun 89 16:38:12 EDT

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

- Prev by Date:
**Algorithm needed for "rationalize"** - Next by Date:
**PASSING DATA FROM TI-SCHEME TO EDWIN** - Previous by thread:
**Algorithm needed for "rationalize"** - Next by thread:
**PASSING DATA FROM TI-SCHEME TO EDWIN** - Index(es):