Xref: utzoo sci.math:6974 comp.lang.scheme:708
Path: utzoo!attcan!uunet!cs.utexas.edu!tut.cis.ohio-state.edu!ukma!gatech!udel!rochester!pt.cs.cmu.edu!andrew.cmu.edu!bobg+
From: bobg+@andrew.cmu.edu (Robert Steven Glickstein)
Newsgroups: sci.math,comp.lang.scheme
Subject: Algorithm needed for "rationalize"
Message-ID: <4YXgcjO00Vsn0Jl0t=@andrew.cmu.edu>
Date: 8 Jun 89 19:34:07 GMT
Followup-To: sci.math
Organization: Information Technology Center, Carnegie Mellon, Pittsburgh, PA
Lines: 25


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