(rationalize x y)

[Alan Bawden <ALAN@AI.AI.MIT.EDU>]

Definition:  A rational r1 is "simpler" than a rational r2, written
r1 <* r2, if r1 = p1/q1 and r2 = p2/q2 (both in lowest terms) and
|p1| <= |p2| and |q1| <= |q2|.

So 1/2 <* 1/3 and 1/2 <* 3/2 but 1/3 and 3/2 are incomparable.  This
definition works for Gaussian rationals as well.

Theorem:  The relation <* is a partial order on rationals.  Also, zero is
simpler than any other rational (0 <* r for all r).

Theorem:  For any two incomparable (under <*) rationals r < s, there exists
a rational t such that r < t < s, and t <* r and t <* s.

Theorem:  Any interval of the real numbers (open, half-open, or closed)
contains a simplest rational number.

I think that the proofs of these theorems are all straightforward enough
that I don't need to give them here.

    Date: Mon, 15 Feb 88 17:41:29 CST
    From: David Bartley <bartley%home.csc.ti.com at RELAY.CS.NET>
    Ed Ferguson and I want to clarify some issues concerning the Scheme
    procedure "rationalize", which is documented in R3RS as follows:

        [...]
        (rationalize x y)				procedure
        (rationalize x)				procedure

        These procedures create integers and rationals.  Their
        results are exact if and only if their arguments are exact.

        [...] With two arguments, RATIONALIZE produces the rational
        number with smallest denominator differing from X by no more
        than Y.  With one argument, RATIONALIZE produces the best
        rational approximation to X, preserving all of the precision in
        its representation.

    (1) When Y is supplied and is non-zero, it would seem more proper to
    return an inexact result (unless perhaps that result is `=' to X and X
    is exact).

The phrase "the rational number with smallest denominator" unfortunately
leaves RATIONALIZE slightly underspecified.  (RATIONALIZE 3/2 1) is free to
be either 1 or 2, since they both have a denominator of 1.  I presume that
what R3RS is trying to say is that (RATIONALIZE X Y) returns the simplest
rational number in the interval [X-Y, X+Y].  (When there is a unique
rational number with smallest denominator it is also the simplest.)

Since the theorem above guarantees the uniqueness and existence of a
simplest rational, it would seem to me that if X and Y are exact, then the
answer should be exact as well.

It is less clear to me what R3RS is trying to say that the one argument
case of RATIONALIZE is supposed to do.  One possible interpretation seems
to be that (RATIONALIZE X) is the same as (RATIONALIZE X #E0), since then
in the case where X is an inexact floating point number, it might well return
the same (inexact) rational that the Common Lisp RATIONALIZE function
returns.  (And if X was an exact floating point number, it might return the
same (exact) rational that the Common Lisp RATIONAL function would return.)

The description doesn't say what should happen if Y is negative...

    (2) Although the notation indicates that the argument X is real, would
    it be frivolous to say that (RATIONALIZE Z Y), where Z is a non-real
    complex number, is defined by

    	(make-rectangular (rationalize (real-part z y))
    			  (rationalize (imag-part z y)))  ?

    Two objections come to mind: (2a) this discriminates against an
    implementation that uses polar representation, and (2b) one might want
    to interpret Y as a error term for the magnitude rather than for the
    real and imaginary parts separately.

I would object because the definition doesn't work.
(RATIONALIZE 2/5+1/5i 1/12) would return 1/3+1/4i.  But in lowest terms
2/5+1/5i is 1/(2-i) and 1/3+1/4i is (4+3i)/12, so the input was a simpler
rational than the output!

    (3) Do we really want an absolute error test or is a relative error
    test sometimes more appropriate?

You can always construct the relative case given the absolute case.  It's
just a way of letting you specify an interval.

    (4) The wording ``rational number with smallest denominator differing
    from X by no more than Y'' seems to rule out using Euclid's algorithm
    and continued fractions.  That is, suppose W is the first number whose
    difference from X is less than Y in the continued fraction series of
    successively better approximations to X.  Euclid doesn't guarantee
    that there is no number within Y of X with smaller denominator than
    W's.  Did the author of these words have a different algorithm in mind?

    As an example, consider (RATIONALIZE 11/16 1/4).  The successive
    convergents to 11/16 using continued fractions are 0, 1, 2/3, and
    11/16.  The first number in that series which is within 1/4 of 11/16
    is 2/3, but the value 1/2 is also within 1/4 of 11/16 and has a
    smaller denominator.

What you do is compute the continued fractions of the two endpoints of the
interval in question.  In this case 7/16 = 0+1/(2+1/(3+1/2)) and 15/16 =
0+1/(1+1/15).  Since the continued fraction of the answer has the same
initial terms as the continued fractions of the endpoints, you stop the
continued fraction expansion as soon as you see that the next term will
differ.  Then the final term is the smallest integer in the interval
between the two remainders.  In this case 7/16 = 0+1/(2+2/7) and 15/16 =
0+1/(1+1/15), so since the smallest integer between 2+2/7 and 1+1/15 is 2,
the answer is 0+1/2 = 1/2.

Since you only need to compute the continued fractions until they differ,
and since you can accumulate the answer as you go, this computation isn't
all that expensive.