[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).
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4