Skip to content

Instantly share code, notes, and snippets.

@mscuthbert
Last active August 29, 2015 14:03
Show Gist options
  • Save mscuthbert/f22942537ebbba2c31d4 to your computer and use it in GitHub Desktop.
Save mscuthbert/f22942537ebbba2c31d4 to your computer and use it in GitHub Desktop.
Get the best speed out of either a float (int) or Fraction object depending on what level of precision is necessary.
from fractions import Fraction
DENOM_LIMIT = 65535
def _preFracLimitDenominator(n, d):
'''
copied from fractions.limit_denominator. Their method
requires creating three new Fraction instances to get one back. this doesn't create any
call before Fraction...
DENOM_LIMIT is hardcoded to defaults.limitOffsetDenominator for speed...
returns a new n, d...
>>> _preFracLimitDenominator(100001, 300001)
(1, 3)
>>> from fractions import Fraction
>>> Fraction(100000000001, 300000000001).limit_denominator(65535)
Fraction(1, 3)
>>> Fraction(100001, 300001).limit_denominator(65535)
Fraction(1, 3)
Timing differences are huge!
t is timeit.timeit
t('Fraction(*_preFracLimitDenominator(*x.as_integer_ratio()))',
setup='x = 1000001/3000001.; from __main__ import preFracLimitDenominator;from fractions import Fraction',
number=100000)
1.0814228057861328
t('Fraction(x).limit_denominator(65535)',
setup='x = 1000001/3000001.; from fractions import Fraction',
number=100000)
7.941488981246948
Proof of working...
>>> import random
>>> myWay = lambda x: Fraction(*_preFracLimitDenominator(*x.as_integer_ratio()))
>>> theirWay = lambda x: Fraction(x).limit_denominator(65535)
>>> for i in range(50):
... x = random.random()
... if myWay(x) != theirWay(x):
... print "boo: %s, %s, %s" % (x, myWay(x), theirWay(x))
(n.b. -- nothing printed)
'''
nOrg = n
dOrg = d
if (d <= DENOM_LIMIT):
return (n, d)
p0, q0, p1, q1 = 0, 1, 1, 0
while True:
a = n//d
q2 = q0+a*q1
if q2 > DENOM_LIMIT:
break
p0, q0, p1, q1 = p1, q1, p0+a*p1, q2
n, d = d, n-a*d
k = (DENOM_LIMIT-q0)//q1
bound1n = p0+k*p1
bound1d = q0+k*q1
bound2n = p1
bound2d = q1
#s = (nOrig, dOrig)
bound1minusS = (abs((bound1n * dOrg) - (nOrg * bound1d)), (dOrg * bound1d))
bound2minusS = (abs((bound2n * dOrg) - (nOrg * bound2d)), (dOrg * bound2d))
difference = (bound1minusS[0] * bound2minusS[1]) - (bound2minusS[0] * bound1minusS[1])
if difference > 0:
# bound1 is farther from zero than bound2; return bound2
return (p1, q1)
else:
return (p0 + k*p1, q0 + k * q1)
def opFrac(num):
'''
opFrac -> optionally convert a number to a fraction or back.
Important music21 2.x function for working with offsets and quarterLengths
Takes in a number (or None) and converts it to a Fraction with denominator
less than limitDenominator if it is not binary expressible; otherwise return a float.
Or if the Fraction can be converted back to a binary expressable
float then do so.
This function should be called often to ensure that values being passed around are floats
and ints wherever possible and fractions where needed.
The naming of this method violates music21's general rule of no abbreviations, but it
is important to make it short enough so that no one will be afraid of calling it often.
It also doesn't have a setting for maxDenominator so that it will expand in
Code Completion easily. That is to say, this function has been set up to be used, so please
use it.
>>> from fractions import Fraction
>>> opFrac(3)
3.0
>>> opFrac(1.0/3)
Fraction(1, 3)
>>> opFrac(1.0/4)
0.25
>>> f = Fraction(1,3)
>>> opFrac(f + f + f)
1.0
>>> opFrac(0.123456789)
Fraction(10, 81)
>>> opFrac(None) is None
True
'''
# This is a performance critical operation, tuned to go as fast as possible.
# hence redundancy -- first we check for type (no inheritance) and then we
# repeat exact same test with inheritence.
t = type(num)
if t is float:
# quick test of power of whether denominator is a power
# of two, and thus representable exactly as a float: can it be
# represented w/ a denominator less than DENOM_LIMIT?
# this doesn't work:
# (denominator & (denominator-1)) != 0
# which is a nice test, but denominator here is always a power of two...
ir = num.as_integer_ratio()
if ir[1] > DENOM_LIMIT: # slightly faster than hardcoding 65535!
return Fraction(*_preFracLimitDenominator(*ir)) # way faster!
else:
return num
elif t is int:
return num + 0.0 # 8x faster than float(num)
elif t is Fraction:
d = num._denominator # private access instead of property: 6x faster; may break later...
if (d & (d-1)) == 0: # power of two...
return num._numerator/(d + 0.0) # 50% faster than float(num)
else:
return num # leave fraction alone
elif num is None:
return None
# class inheritance only check AFTER type(x) if statements...
elif isinstance(num, int):
return num + 0.0
elif isinstance(num, float):
ir = num.as_integer_ratio()
if ir[1] > DENOM_LIMIT: # slightly faster than hardcoding 65535!
return Fraction(*_preFracLimitDenominator(*ir)) # way faster!
else:
return num
elif isinstance(num, Fraction):
d = num._denominator # private access instead of property: 6x faster; may break later...
if (d & (d-1)) == 0: # power of two...
return num._numerator/(d + 0.0) # 50% faster than float(num)
else:
return num # leave fraction alone
else:
return num
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment