用于计算阶乘的快速算法

我发现this page描述了用于计算阶乘的多种算法。不幸的是，解释很简单，我不想通过逐行扫描源代码来理解算法背后的基本原理。用于计算阶乘的快速算法

任何人都可以指出我对这些（或其他快速）算法的更详细的描述来计算阶乘吗？

编辑：This page描述了素因子分解的方法，这是所有性能最好的因子算法通用的技术。它还包含一些Python中很好的示例代码。作者链接到a description of binary splitting，并引用算法杂志（“关于计算因子的复杂性”）的文章，看起来很有前途，如果我只能得到它的话。

来源

2009-11-17 ThisSuitIsBlackNot

如果你的因子很大，并且你想要一个近似值，不要忘记斯特林的近似值。我注意到它没有在该页面中提及。 http://en.wikipedia.org/wiki/Stirling%27s_approximation – Rooke 2009-11-17 20:02:29

@Rooke：我正在计算大的因式分解......或许我应该在我的问题上更清楚。还是）感谢你的建议！ – ThisSuitIsBlackNot 2009-11-17 21:16:43

你也可以试试我的[Fast exact bigint factorial]（https://stackoverflow.com/a/18333853/2521214） – Spektre 2017-12-28 09:47:31

查看Richard Fateman的paper (PDF link)。代码示例在Lisp中，但是在任何情况下，大部分秘密归结为最小化必须完成的bignum（任意精度整数）计算的次数。

当然，如果你不需要/有白葡萄酒，它是微不足道的;查找表或简单的循环都可以。

编辑：如果你可以使用一个大概的答案，您可以直接通过总结log(k)为k = 2 ... n，或使用古老的Stirling approximation计算阶乘的对数。您希望尽可能使用对数来避免溢出;特别是斯特林近似的天真应用会在许多不需要的地方溢出。

来源

2009-11-17 20:03:44 Pillsy

+1：这篇文章非常有帮助（虽然我的Lisp有点生疏）。不幸的是，看起来Luschny是更复杂算法的首选人员，所以我可能会被困在他的源代码中。 – ThisSuitIsBlackNot 2009-11-17 21:13:56

还有另一种方法。这种方法是详细的here，减半乘以一点点的加法和减法。你可能想要显示第一个方法，如果你能理解，显示的第二个方法是一个有趣的阅读。

来源

2013-04-15 02:01:36 user2035846

用于计算阶乘的快速算法

回答

相关问题