algorithm - 计算阶乘的快速算法

Question

我发现这个页面描述了一些计算阶乘的算法。不幸的是，解释很简洁，我不想逐行筛选源代码来理解算法背后的基本原理。

谁能指出我对这些（或其他快速）计算阶乘算法的更详细描述？

编辑： 此页面描述了素数分解的方法，这是所有性能最佳的阶乘算法共有的技术。它还包含一些不错的 Python 示例代码。作者链接到二进制拆分的描述，并引用了Journal of Algorithms中的一篇文章（“On the Complexity of Calculating Factorials”），如果我能得到它，它看起来很有希望。

Answer 1

查看 Richard Fateman 的这篇论文（PDF 链接）。代码示例在 Lisp 中，但无论如何，大部分秘密归结为最小化您必须执行的 bignum（任意精度整数）计算的数量。

自然，如果您不需要/没有 bignums，那是微不足道的；查找表或简单的循环都可以。

编辑：如果您可以使用近似答案，您可以直接通过求和log(k)来计算阶乘的对数k = 2 ... n，或者使用古老的斯特林近似值。您希望尽可能使用对数以避免溢出；特别是，斯特林近似的幼稚应用会在很多不需要的地方溢出。

Answer 2

还有另一种方法。此处详细介绍了此方法，该方法将乘法量减半，只需一点点加法和减法。您可能希望显示第一种方法，如果您能理解，显示的第二种方法是一本有趣的书。

Answer 3

十多年后，我想提供一种 Python 方法，灵感来自于你对乘法感兴趣，factorial(n) * n+1基本情况是0，1结果是1，那么：

def fact_var(num):
    a, b, i = 1,2,2 # base cases and our i counter.
    while i < num: # if i is equal to num, we're done, last product will be at return.
        c = a * b # start to multiply and save in c.
        i+=1 # add 1 to i because we want to multiply next number with c (in the next iteration).
        a, b = c, i # update variables to the next iteration.
    return a * b if num > 1 else 1 # last product occurs here is num is greater than 1.

print(fact_var(100000))

对于 100 000 的阶乘，在我的机器上最多需要 5 秒，我希望它可以为文档和即将到来的观众服务！

附言。同样的想法对计算斐波那契很有用，斐波那契是求和而不是乘法。