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

[M.-A. Lemburg]

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 <wink>:  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 max_d.  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 max_d 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/