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/
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