[pypy-issue] [issue1654] math.factorial is slow
anon
tracker at bugs.pypy.org
Sat Dec 7 00:25:46 CET 2013
New submission from anon <b10419697 at klzlk.com>:
math.factorial uses a very simple algorithm multiplying by each value in
range(1,x+1) in turn. A better method would be to do binary splitting. I am
unfamiliar with PyPy internals, however I believe app_math.py implements
factorial in pure Python.
Provided below is a patch that uses binary splitting. It seems much faster for
large factorials, but maybe uses slightly more memory and seems 10% slower for
very small factorials.
def factorial(x):
"""Find x!."""
if isinstance(x, float):
fl = int(x)
if fl != x:
raise ValueError("float arguments must be integral")
x = fl
#Experimentally this gap seems good
gap = max(100, x>>7)
def _fac(low, high):
if low+gap >= high:
t = 1
for i in range(low, high):
t *= i
return t
mid = (low + high) >> 1
return _fac(low, mid) * _fac(mid, high)
return _fac(1, x+1)
If someone can improve it further, that would be great. The code is public domain.
----------
messages: 6402
nosy: anon, pypy-issue
priority: performance bug
status: unread
title: math.factorial is slow
________________________________________
PyPy bug tracker <tracker at bugs.pypy.org>
<https://bugs.pypy.org/issue1654>
________________________________________
More information about the pypy-issue
mailing list