10

这是我对阶乘的方法：

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

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

4

9 回答 9

26

将数字按顺序相乘，

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

所以对于100000!.

于 2013-05-01T21:44:33.553 回答
10

阶乘变得非常大，因此处理数字的对数通常会更好。

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

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

您可以除以 log10 以将其转换为以 10 为底的对数。

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

from math import *
print ceil(lgamma(100000+1)/log(10))
于 2013-05-01T21:07:42.723 回答
7

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

于 2013-05-01T20:40:26.907 回答
3

如果您只需要一个近似值，Ramanujan 的阶乘近似应该比斯特林的更准确。

如果您需要（或想要）精确的东西，您可以尝试 GMP，即 GNU 多精度库。我已经成功地将它用于 Python 中大数的素性测试。

于 2013-05-02T00:02:29.037 回答
1

您可以使用 reduce 函数而不是显式循环：

>>> from functools import reduce
>>> mul = int.__mul__
>>> len(str(reduce(mul, range(2,100001), 1)))
456574
>>>

在 Python 2 中，您需要使用 longs:long.__mul__和len(str(reduce(mul, range(2L,100001L), 1L)))

于 2013-05-02T06:47:53.463 回答
1

真正需要真正的阶乘值 n 实际上是不寻常的！在许多应用领域。通常使用阶乘的自然对数更为现实。我想不出任何不能将日志用作更好选择的应用程序，因为阶乘最常用于计算与选择事物组合的概率相关的值。

一个常见的计算是基于阶乘的概率，例如选择二项式系数 (nk) = n！/（k！（nk）！）。鉴于这是阶乘的比率，则 log(nk) = log(n!)-log(k!)-log((nk)!) 可以使用各种对数阶乘近似值之一可靠地计算。而且，如果您进行大量概率数学运算，通常最好在对数域中进行（以分贝为单位测量概率），因为它通常涉及小于 1 的极宽范围的数字，因此使用常见的数学精度会很快崩溃如果不使用日志版本，则使用浮点表示。

ETJaynes 是一位著名的数学家和概率论专家，我推荐他的书“概率论：科学的逻辑”作为该主题以及使用对数概率的贝叶斯推理和信息论的非常易读的资料。

于 2019-02-17T09:38:11.013 回答
0

由二次效应引起的减速：随着 n 变大，您必须进行更多的乘法运算，但您也必须乘以更大的数字。

找到更好的算法并不容易。您可以尝试利用对称性（如在 FFT 中）。以不同的顺序进行乘法运算也很划算，结果是中间结果，这样你最终只会乘以几个非常大的数字，但我还没想到最后。无论如何，你必须找到一个可以利用的法律。

在这里寻找更多灵感。

于 2013-05-01T20:59:24.450 回答
0

您可以返回 gamma 函数 ( math.gamma(x))，但使用 for 循环生成阶乘可能会更快

于 2013-05-01T20:55:11.783 回答
0

你确实意识到阶乘（100000）大约是2.8242294080 ×10^456,573
这就是为什么它很慢，它很大。

于 2013-05-01T20:34:20.867 回答