在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

将数字乘以顺序,

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!.

Answer 2

如果您需要较短的执行时间并且不需要最佳精度,则可以使用近似公式,例如斯特林近似

Answer 3

因子变得非常大,因此处理数字的对数通常更好.

许多语言都有一个lgamma库函数,它可以计算n-1阶乘的自然对数.

这意味着您可以通过lgamma(n + 1)计算阶乘(n)的自然对数.

您可以除以log10将其转换为基数10对数.

因此,如果您只想要数字位数,那么这个Python代码将立即给出答案:

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

Answer 4

您确实意识到阶乘（100000）大约为2.8242294080\xc3\x9710^456,573
\n这就是为什么它很慢，它很大。

\n