Factorials

[Anton Vredegoor]

Gerhard Häring <gh at ghaering.de> wrote:

>If you're doing a lot with factorials, I think you should upgrade to 
>Python 2.3 already, because it has an optimized multiplication for longs.

Yes, but for small ints there is negative speed improvement, so turbo
mode is only enabled for big ints? If that's correct then one has to
aggregate into bigger ints first to get real benefit. Using 2**2000 as
a treshold value is based on my personal experimental truth only and
probably I'm overdoing it a bit. However, the code below seems to be a
way to use optimized multiplication for longs for large factorials and
still keep good performance for small values.

Anton

import profile
from operator import mul

def fac(n): return reduce(mul,range(2,n+1),1)

def karagen(n):
    K = 2**2000
    y = 1
    for x in xrange(2,n+1):
        y *= x
        if y > K:
            yield y
            y = 1
    yield y
        
def fac1(n):
    R = [x for x in karagen(n)]
    while len(R) > 1:
        if len(R) % 2 <> 0 : R[0] *= R.pop()
        R = [x*y for x,y in zip(R[::2],R[1::2])]
    return  R[0]

def main():
    n = 10000
    assert fac(n) == fac1(n)
    
def test():
    profile.run("main()")

if __name__=='__main__':
    test()