http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52317
Here's a script of mine that compares the results of farey() with bestFracForMaxDenom(), from my frac.py (at <http://www.rcblue.com/Python/fracForWeb.py>):
The maxDenom (the lim of farey()) is set at 100.
The dec, or decimal, or value, or v of farey(), is generated for each case by random.uniform(0.1, 1).
==============================================
#compareFracAndFarey.py
from __future__ import division
import random
def bestFracForMaxDenom(decimal, maxDenom):
leastError = 1
for denom in xrange(1, maxDenom + 1):
num = round(decimal * denom)
error = abs((num / denom - decimal) / decimal)
if error < leastError:
leastError = error
bestDenom = denom
bestNum = int(num)
# leastError is a float; should I have this if statement?
if leastError == 0:
break
return bestNum, bestDenom, leastError
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 # get 0 of right type for denominator
lower, upper = (z,z+1), (z+1,z)
#print lower, upper
while True:
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
maxDenom = 100
count = 0
for x in range(10):
dec = random.uniform(0.1, 1)
num1, denom1, leastError = bestFracForMaxDenom(dec, maxDenom)
num2, denom2 = farey(dec, maxDenom)
if (num1 != num2) or (denom1 != denom2):
count += 1
print "Case", count
print "When value is", dec, "and lim is", maxDenom
print "frac.py fraction is %d/%d" % (num1, denom1)
print "frac.py error is", num1/denom1 - dec
print "farey.py fraction is %d/%d" % (num2, denom2)
print "farey.py error is", num2/denom2 - dec
=================end of compareFracAndFarey.py==========================
(compareFracAndFarey.py is also on the web, at <http://www.rcblue.com/Python/compareFracAndFarey_ForWeb.py>)
Here's the result of one run, that notes the 3 of 10 pairs of results in which the farey() fraction is different from the bestFracForMaxDenom() fraction. Of course, I believe that the bestFracForMaxDenom() fractions are correct, but check them out for yourselves.
Case 1
When value is 0.834489320423 and lim is 100
frac.py fraction is 81/97
frac.py error is 0.000562225968725
farey.py fraction is 5/6
farey.py error is -0.00115598708969
Case 2
When value is 0.584115140346 and lim is 100
frac.py fraction is 52/89
frac.py error is 0.000154522575557
farey.py fraction is 7/12
farey.py error is -0.000781807012458
Case 3
When value is 0.946959063604 and lim is 100
frac.py fraction is 89/94
frac.py error is -0.000150552966002
farey.py fraction is 18/19
farey.py error is 0.000409357448332
Dick Moores
_______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
