New submission from Stefan Behnel:
fractions.gcd() is required for normalising numerator and denominator of the
Fraction data type. Some speed improvements were applied to Fraction in issue
22464, now the gcd() function takes up about half of the instantiation time in
the benchmark in issue 22458, which makes it quite a heavy part of the overall
Fraction computation time.
The current implementation is
def gcd(a, b):
while b:
a, b = b, a%b
return a
Reimplementing it in C would provide for much faster calculations. Here is a
Cython version that simply drops the calculation loop into C as soon as the
numbers are small enough to fit into a C long long int:
def _gcd(a, b):
# Try doing all computation in C space. If the numbers are too large
# at the beginning, retry until they are small enough.
cdef long long ai, bi
while b:
try:
ai, bi = a, b
except OverflowError:
pass
else:
# switch to C loop
while bi:
ai, bi = bi, ai%bi
return ai
a, b = b, a%b
return a
It's substantially faster already because the values will either be small
enough right from the start or quickly become so after a few iterations with
Python objects.
Further improvements should be possible with a dedicated PyLong implementation
based on Lehmer's GCD algorithm:
https://en.wikipedia.org/wiki/Lehmer_GCD_algorithm
----------
components: Library (Lib)
messages: 227487
nosy: scoder
priority: normal
severity: normal
status: open
title: Speed up fractions.gcd()
type: performance
versions: Python 3.5
_______________________________________
Python tracker <rep...@bugs.python.org>
<http://bugs.python.org/issue22486>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
