计算阶乘的快速算法
我发现this page描述了许多用于计算阶乘的算法。不幸的是，解释很简洁，我不想逐行筛选源代码来理解算法背后的基本原理。
谁能告诉我这些(或其他快速的)计算阶乘的算法的更详细的描述？
编辑： This page描述了素数分解的方法，这是所有性能最好的阶乘算法共同使用的技术。它还包含一些用Python编写的很好的示例代码。作者链接到a description of binary splitting并引用了算法杂志上的一篇文章(“关于计算阶乘的复杂性”)，这篇文章看起来很有希望，如果我能拿到它的话。
回答 3
Stack Overflow用户
发布于 2009-11-18 04:03:44
看看这是理查德·法特曼写的paper (PDF link)。代码示例是用Lisp编写的，但无论如何，许多秘密归结为最小化您必须进行的bignum (任意精度整数)计算的数量。
当然，如果您不需要/没有bignums，那么它是微不足道的；一个查找表或一个简单的循环就可以了。
编辑:如果您可以使用近似答案，则可以直接通过对log(k) k = 2 ... n求和来计算阶乘的对数，或者使用古老的Stirling approximation。您希望尽可能地使用对数来避免溢出；特别是，Stirling近似的幼稚应用程序将在许多不需要溢出的地方溢出。
Stack Overflow用户
发布于 2013-04-15 10:01:37
还有另一种方法。这种方法是详细的here，通过少量的加法和减法将乘法的数量减半。您可能想要显示第一个方法，如果您能够理解第二个方法，那么第二个方法将是一个有趣的读物。
Stack Overflow用户
发布于 2021-12-20 22:33:12
十多年后，我想提供一种Python方法，灵感来自于您对multiply 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))对于100000的阶乘，在我的机器上需要5秒，我希望它能为文档和即将到来的查看器服务！
Ps。同样的想法对计算斐波那契也很有用，斐波那契是一个求和而不是乘法。
https://stackoverflow.com/questions/1751334
复制相似问题