algorithm - 计算阶乘的快速算法

Question

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

任何人都可以指出这些(或其他快速)算法的更详细描述，以快速计算大的精确阶乘吗？

Factorials with prime factorization (Python) 描述素因式分解的方法，这是所有性能最佳的阶乘算法通用的技术。它还包含一些很好的 Python 示例代码。作者链接a description of binary splitting并引用了算法杂志中的一篇文章(“关于计算阶乘的复杂性”)，如果我只能得到我的hands on，那篇文章看起来很有前途。

Answer 1

看看这个 paper (PDF link)理查德·法特曼着。代码示例在 Lisp 中，但无论如何，大部分 secret 归结为最小化您必须执行的 bignum(任意精度整数)计算的数量。

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

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