(rationalize x y)

[David Bartley <bartley%home.csc.ti.com@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).

(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.

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

(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.

Regards,
David Bartley