python中的大数阶乘

Question

下面是我的阶乘方法：

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

我觉得这很简单，不过我想你可以做一些更有效率的事情，因为像100000这样的大数字需要很长时间。我的问题是，有吗？math.factorial（）也不好，它花费的时间大致相同。

Answer 1

阶乘变得非常大，所以处理数字的对数通常更好。

许多语言都有一个计算n-1阶乘自然对数的lgama库函数。

这意味着您可以通过lgama（n+1）计算阶乘（n）的自然对数。

你可以除以log10把它变成以10为底的对数。

因此，如果您只需要位数，那么这个Python代码将立即给出答案：

from math import *
print ceil(lgamma(100000+1)/log(10))

Answer 2

把数字按顺序相乘

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

因此100000!的加速比超过10倍。

Answer 3

如果需要较短的执行时间并且不需要尽可能高的精度，可以使用近似公式，例如Stirling approximation