[pypy-issue] [issue1654] math.factorial is slow

[anon]

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
    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 <tracker at bugs.pypy.org>
<https://bugs.pypy.org/issue1654>
________________________________________