快速算法计算阶乘 [英] Fast algorithms for computing the factorial

问题描述

我发现此页面描述计算阶乘一些算法。不幸的是，解释是简洁的，我不喜欢的来源$ C ​​$ C线后，通过行筛选，了解算法背后的基本原理。

I found this page describing a number of algorithms for computing the factorial. Unfortunately, the explanations are terse and I don't feel like sifting through line after line of source code to understand the basic principles behind the algorithms.

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

Can anybody point me to more detailed descriptions of these (or other fast) algorithms for computing the factorial?

编辑： 本页面介绍的方法素分解，通用于所有的表现最好的阶乘算法的技术。它也包含了一些很好的例子code Python编写的。作者链接的二元分裂说明和引用在杂志的一篇文章算法的（关于计算阶乘的复杂性），看起来很有希望，只要我能得到我的手就可以了。

This page describes the method of prime factorization, the technique common to all of the best-performing factorial algorithms. It also contains some nice example code in Python. The author links to a description of binary splitting and references an article in the Journal of Algorithms ("On the Complexity of Calculating Factorials") that looks promising, if I could only get my hands on it.

推荐答案

看看这个论文（PDF格式链接）由Richard Fateman 的。在code样品是用Lisp中，但在任何情况下，大部分的秘诀归结为减少BIGNUM数（任意precision整数），你所要做的计算。

Check out this paper (PDF link) by Richard Fateman. The code samples are in Lisp, in but in any event, much of the secret boils down to minimizing the number of bignum (arbitrary precision integer) calculations you have to do.

当然，如果你不需要/有大数，这是微不足道的;无论是查找表或一个简单的循环将被罚款。

Naturally, if you don't need/have bignums, it's trivial; either a lookup table or a simple loop will be fine.

编辑：如果你可以用一个近似的回答，您可以直接通过总结日志（K）的计算阶乘的对数 K = 2，...，N ，或使用古老的斯特林近似。要与对数尽可能避免溢出工作;特别是，斯特灵公式的幼稚应用将溢出在很多地方没有的地方。

If you can use an approximate answer, you can either compute the logarithm of the factorial directly by summing log(k) for k = 2 ... n, or by using the venerable Stirling approximation. You want to work with the logarithm wherever possible to avoid overflow; in particular, a naive application of Stirling's approximation will overflow in a lot of places where it doesn't have to.

这篇关于快速算法计算阶乘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！