用于计算阶乘的快速算法

Question

我发现这个页面描述了许多用于计算阶乘的算法.不幸的是,解释很简洁,我不想逐行筛选源代码来理解算法背后的基本原理.

任何人都能指出我对这些(或其他快速)计算因子的算法的更详细描述吗？

编辑: 此页面描述了素数因子分解的方法,这是所有性能最佳的因子算法共有的技术.它还包含Python中的一些很好的示例代码.作者链接到二进制分裂的描述,并参考了算法杂志("计算因子的复杂性")中的一篇文章,看起来很有希望,如果我只能得到它.

Answer 1

查看Richard Fateman撰写的这篇论文(PDF链接).代码示例在Lisp中,但无论如何,大部分秘密归结为最小化你必须做的bignum(任意精度整数)计算的数量.

当然,如果你不需要/有bignums,它是微不足道的; 查找表或简单循环都可以.

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

Answer 2

还有另一种方法.这里详细说明了这种方法,将一点加法和减法的乘法量减半.您可能想要显示第一个方法,如果您能理解,则显示的第二个方法是一个有趣的读取.