[Python-Dev] Re: PEP239 (Rational Numbers) Reference Implementation and new issues (original) (raw)

M.-A. Lemburg mal@lemburg.com
Fri, 04 Oct 2002 19:04:48 +0200

Tim Peters wrote:

[Fran=E7ois Pinard] =20

... Interesting, I'll save it. I use continued fraction expansion to get the "best" rational fitting a float within a tolerance, and wonder how Farey will be similar/different. Tim will surely tell us, out of his head! :-) =20 =20 Your wish is granted : Moshe Zadka's prototype implementation of rationals is still sitting in Python CVS nondist/sandox/rational/. Its trim function is one I worked on with him, and uses c.f. expansion to = find "the best" rational approximating a given rational, among all rationals= with denominator no larger than argument maxd. The Farey method is almost identical, except potentially much slower. It's almost what "the usual= " continued fraction algorithm would do if you couldn't use integer divis= ion to do a whole bunch of steps in one gulp; e.g., whenever the c.f. expan= sion gets a partial quotient of N, the Farey method does N distinct steps.=20

But isn't division much more costly than addition and multiplication if you have long integers to deal with ? (I can't tell, because the works are done by GMP in mxNumber)

About "almost identical": c.f. expansion produces a sequence of rationals alternately smaller and larger than the target, each one (much) closer = than the last. The Farey method also looks at rationals "between" those; t= rim does too, but only at the endpoint, when maxd is between the denominat= ors of two successive c.f. convergents. =20 Moshe's package also has an approximate function, to find "the smalles= t" rational within a given absolute distance of an input rational; that's probably closest to what you're doing now. trim answers questions lik= e "what's the best approximation to pi with denominator no greater than 6= ?". Neither of the adjacent convergents 3/1 and 22/7 is the correct answer = to that; 19/6 is correct. Note that the c.f. expansion gets 22/7 because = the previous two convergents were 1/0 and 3/1, the next partial quotient is= 7, and then the next convergent is =20 1 + 3*7 22 ------- =3D -- 0 + 1*7 7 =20 If the partial quotient had been 6, it would have given 19/6 instead. That's what the tail end of trim deduces. =20 The Farey method does this one step at a time, going from (and skipping= to then end of process) =20 1/0 3/1 =20 as bounds to =20 3/1 4/1 =20 and then =20 3/1 7/2 =20 and then =20 3/1 10/3 =20 and then =20 3/1 13/4 =20 and then =20 3/1 16/5 =20 and then, finally =20 3/1 19/6 =20 Especially when coded in Python, it's much more efficient to deduce thi= s in one gulp (via exploiting division).

How useful are .trim() and .approximate() in practice ? If they are, then I could put them on the TODO list for mxNumber.

--=20 Marc-Andre Lemburg CEO eGenix.com Software GmbH

eGenix.com -- Makers of the Python mx Extensions: mxDateTime,mxODBC,... Python Consulting: http://www.egenix.com/ Python Software: http://www.egenix.com/files/python/