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

# Algorithm needed for "rationalize"

```I am writing a Scheme interpreter based in the Revised^3.95 Report on
Scheme.  I am unable to find or devise an algorithm for the
"rationalize" procedure.  Rationalize operates on two real, rational or
integral numbers.  To quote the report:

(rationalize x y)

Rationalize returns the *simplest* rational number differing
from x by no more than y.  A rational number r1 is *simpler*
than another rational number r2 if r1 = p1/q1 and r2 = p2/q2 (in
lowest terms) and |p1| <= |p2| and |q1| <= |q2|.  Thus 3/5 is
simpler than 4/7.  Although not all rationals are comparable in
this ordering (consider 2/7 and 3/5) any interval contains a
rational number that is simpler than every other rational number
in that interval (the simpler 2/5 lies between 2/7 and 3/5).
Note that 0 = 0/1 is the simplest rational of all.

Thanks in advance.

Bob Glickstein, ITC Database Group
Information Technology Center
Carnegie Mellon University
Pittsburgh, PA
```