[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
(rationalize x y)
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
(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
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
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.