New submission from anon <[email protected]>:
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
if x < 0:
raise ValueError("x must be >= 0")
#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.
________________________________________
PyPy bug tracker <[email protected]>
<https://bugs.pypy.org/issue1654>
________________________________________
_______________________________________________
pypy-issue mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-issue
