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

[Tim Peters]

[Fran=E7ois Pinard]
> ...
> 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! :-)

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 fi=
nd
"the best" rational approximating a given rational, among all rationals w=
ith
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 divisio=
n
to do a whole bunch of steps in one gulp; e.g., whenever the c.f. expansi=
on
gets a partial quotient of N, the Farey method does N distinct steps.  Ab=
out
"almost identical":  c.f. expansion produces a sequence of rationals
alternately smaller and larger than the target, each one (much) closer th=
an
the last.  The Farey method also looks at rationals "between" those; _tri=
m
does too, but only at the endpoint, when max_d is between the denominator=
s
of two successive c.f. convergents.

Moshe's package also has an _approximate function, to find "the smallest"
rational within a given absolute distance of an input rational; that's
probably closest to what you're doing now.  _trim answers questions like
"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 th=
e
previous two convergents were 1/0 and 3/1, the next partial quotient is 7=
,
and then the next convergent is

    1 + 3*7   22
    ------- =3D --
    0 + 1*7    7

If the partial quotient *had* been 6, it would have given 19/6 instead.
That's what the tail end of _trim deduces.

The Farey method does this one step at a time, going from (and skipping t=
o
then end of process)

   1/0 3/1

as bounds to

   3/1 4/1

and then

   3/1 7/2

and then

   3/1 10/3

and then

   3/1 13/4

and then

   3/1 16/5

and then, finally

   3/1 19/6

Especially when coded in Python, it's much more efficient to deduce this =
in
one gulp (via exploiting division).