python中大数的阶乘

这是我的阶乘方法：

def factorial(n):
    '''Returns factorial of n'''
    r = 1
    for i in range(1, n + 1):
        r *= i
    return r

我认为这非常简单，但我猜你可以做得更有效，因为像 100000 这样的大数字需要很长时间。我的问题是，有吗？ math.factorial() 也不好，它花费的时间大致相同。

按顺序将数字相乘，

r = 1
for i in range(1, n + 1):
    r *= i
return r

非常快地创建一个大数（如数万位），然后您会进行大量的一个大数和一个小数的乘法。至少有一个因子很大的乘法运算速度很慢。

例如，您可以通过减少涉及大量数字的乘法次数来大大加快速度

def range_prod(lo,hi):
    if lo+1 < hi:
        mid = (hi+lo)//2
        return range_prod(lo,mid) * range_prod(mid+1,hi)
    if lo == hi:
        return lo
    return lo*hi

def treefactorial(n):
    if n < 2:
        return 1
    return range_prod(1,n)

产生，计时计算100000! % 100019（我首先尝试len(str(fun(100000))，但是转换为字符串的速度非常慢，因此这使得差异看起来比实际情况要小）：

$ python factorial.py 
81430
math.factorial took 4.06193709373 seconds
81430
factorial took 3.84716391563 seconds
81430
treefactorial took 0.344486951828 seconds

所以加速超过 10 倍100000!.