|
|
 |
|
Title: farey: Numeric to rational via Farey fractions
Submitter: Scott David Daniels
(other recipes)
Last Updated: 2001/04/02
Version no: 1.0
Category:
Algorithms
|
|
 1 vote(s)
|
|
|
|
Description:
This converts a Numeric to a rational. The result is always
in reduced form, but the proof, while possible, is subtle.
farey(math.pi,100) = (22,7)
Source: Text Source
def farey(v, lim):
'''Named after James Farey, an English surveyor.
No error checking on args -- lim = max denominator,
results are (numerator, denominator), (1,0) is infinity
'''
if v < 0:
n,d = farey(-v, lim)
return -n,d
z = lim-lim
lower, upper = (z,z+1), (z+1,z)
while 1:
mediant = (lower[0] + upper[0]), (lower[1]+upper[1])
if v * mediant[1] > mediant[0]:
if lim < mediant[1]: return upper
lower = mediant
elif v * mediant[1] == mediant[0]:
if lim >= mediant[1]: return mediant
if lower[1] < upper[1]: return lower
return upper
else:
if lim < mediant[1]: return lower
upper = mediant
Discussion:
|
|
Add comment
|
|
Number of comments: 3
notes on farey, Scott David Daniels, 2001/04/06
Note the trickiness with "z" -- it is a zero of the same type as the argument lim. This allows you to use longs as the limit if need be.
To print "odds": n,d = farey(probability,lim)
print "Odds are %d : %d" % (n,d-n)
This code is ideally suited for re-implementation in a lower level language (say C or assembly) if you have the need or desire for rational or "odds" output. Because this uses only multiplication and addition, it can play to hardware strengths.
If you are using this in an environment where you call it with a lot of values very near 0., 1., or 0.5 (or _very_ simple fractions), you may find it too slow. You may improve its performance in a "continued fraction" style by appending to the first if:
if v Note the trickiness with "z" -- it is a zero of the same type as the argument lim. This allows you to use longs as the limit if need be.
To print "odds": n,d = farey(probability,lim)
print "Odds are %d : %d" % (n,d-n)
This code is ideally suited for re-implementation in a lower level language (say C or assembly) if you have the need or desire for rational or "odds" output. Because this uses only multiplication and addition, it can play to hardware strengths.
If you are using this in an environment where you call it with a lot of values very near 0., 1., or 0.5 (or _very_ simple fractions), you may find it too slow. You may improve its performance in a "continued fraction" style by appending to the first if:
if v
Add comment
Continued fractions, Connelly Barnes, 2005/10/15
Alternatively, you can use continued fractions: http://mathworld.wolfram.com/ContinuedFraction.html . Note that in the continued fraction, you can use subtractions as well as additions. Thus math.pi == 3+1/(7+1/(16-.003405593314)) ~= 3+1/(7+1/16.) == 355./113.
Add comment
farey() often gives incorrect result, Dick Moores, 2007/01/04
For example, farey(0.36, 10) returns (1, 3), whereas (3, 8) is correct.
For another, farey(0.584115140346, 100) returns (7, 12) whereas (52, 89) is correct.
Dick Moores
rdmoores@gmail.com
Add comment
|
|
|
|
|
|
|
