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

*To*: bartley%home.csc.ti.com@RELAY.CS.NET*Subject*: (rationalize x y)*From*: Alan Bawden <ALAN@AI.AI.MIT.EDU>*Date*: Tue, 16 Feb 88 14:08:28 EST*cc*: rrrs-authors@MC.LCS.MIT.EDU*In-reply-to*: Msg of Mon 15 Feb 88 17:41:29 CST from David Bartley <bartley%home.csc.ti.com at RELAY.CS.NET>

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.

- Prev by Date:
**Re: call for standardization meeting** - Next by Date:
**DO in Scheme** - Prev by thread:
**(rationalize x y)** - Next by thread:
**DO in Scheme** - Index(es):