blocks|key|327819|text|看看这是理查德·法特曼写的paper+(PDF+link)。代码示例是用Lisp编写的，但无论如何，许多秘密归结为最小化您必须进行的bignum+(任意精度整数)计算的数量。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|327820|当然，如果您不需要/没有bignums，那么它是微不足道的；一个查找表或一个简单的循环就可以了。|327821|编辑:如果您可以使用近似答案，则可以直接通过对log(k)++k+=+2+...+n求和来计算阶乘的对数，或者使用古老的Stirling+approximation。您希望尽可能地使用对数来避免溢出；特别是，Stirling近似的幼稚应用程序将在许多不需要溢出的地方溢出。|style|BOLD|CODE|327822|entityMap|0|LINK|mutability|MUTABLE|url|http://www.cs.berkeley.edu/~fateman/papers/factorial.pdf|1|http://mathworld.wolfram.com/StirlingsApproximation.html^0|D|G|0|0|0|0|T|N|6|V|B|1O|M|1|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@$A|V|B|W|1|X]]|C|$]]|$1|D|3|E|5|6|7|Y|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|Z|8|@$A|10|B|11|H|I]|$A|12|B|13|H|J]|$A|14|B|15|H|J]]|9|@$A|16|B|17|1|18]]|C|$]]|$1|K|3|-4|5|6|7|19|8|@]|9|@]|C|$]]]|L|$M|$5|N|O|P|C|$Q|R]]|S|$5|N|O|P|C|$Q|T]]]]

Check out this <a href="http://www.cs.berkeley.edu/~fateman/papers/factorial.pdf" rel="noreferrer">paper (PDF link)</a> 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. 

EDIT: If you can use an approximate answer, you can either compute the logarithm of the factorial directly by summing <code>log(k)</code> for <code>k = 2 ... n</code>, or by using the venerable <a href="http://mathworld.wolfram.com/StirlingsApproximation.html" rel="noreferrer">Stirling approximation</a>. 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.

blocks|key|327875|text|还有另一种方法。这种方法是详细的here，通过少量的加法和减法将乘法的数量减半。您可能想要显示第一个方法，如果您能够理解第二个方法，那么第二个方法将是一个有趣的读物。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|327876|entityMap|0|LINK|mutability|MUTABLE|url|http://sites.google.com/site/examath/research/factorials^0|G|4|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

There is also another method. This method is detailed <a href="http://sites.google.com/site/examath/research/factorials" rel="noreferrer">here</a> that halves the amount of multiplication for a little bit of addition and subtraction. You probably want the first method shown, and the second method shown is an interesting read if you can understand it.

blocks|key|3078466|text|十多年后，我想提供一种Python方法，灵感来自于您对multiply+factorial(n)+*+n%2B1感兴趣，基本情况是0和1，它们的结果是1，然后：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|3078467|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%2B=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))|code-block|syntax|javascript|3078468|对于100000的阶乘，在我的机器上需要5秒，我希望它能为文档和即将到来的查看器服务！|3078469|Ps。同样的想法对计算斐波那契也很有用，斐波那契是一个求和而不是乘法。|3078470|entityMap^0|10|I|1R|1|1T|1|21|1|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@$9|R|A|S|B|C]|$9|T|A|U|B|C]|$9|V|A|W|B|C]|$9|X|A|Y|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|Z|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|10|8|@]|D|@]|E|$]]|$1|M|3|N|5|6|7|11|8|@]|D|@]|E|$]]|$1|O|3|-4|5|6|7|12|8|@]|D|@]|E|$]]]|P|$]]

More than ten years later, I would like to provide a Python approach inspired in the fact that you're interested in multiply <code>factorial(n) * n+1</code> and the base cases are <code>0</code> and <code>1</code> whose result is <code>1</code>, then:
<pre><code>def fact_var(num):
 a, b, i = 1,2,2 # base cases and our i counter.
 while i &lt; 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 &gt; 1 else 1 # last product occurs here is num is greater than 1.

print(fact_var(100000))
</code></pre>
For factorial of 100 000 it takes up to 5 seconds in my machine, I hope it serves for documentation and upcoming viewers!
Ps. Same idea is useful to compute fibonacci, which is a summation not a multiplication.

I found <a href="http://www.luschny.de/math/factorial/FastFactorialFunctions.htm" rel="noreferrer">this page</a> 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?

Edit: <a href="http://en.literateprograms.org/Factorials_with_prime_factorization_&#40;Python&#41;" rel="noreferrer">This page</a> 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 href="http://numbers.computation.free.fr/Constants/Algorithms/splitting.html" rel="noreferrer">a description of binary splitting</a> 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.

Fast algorithms for computing the factorial

Python

我发现描述了许多用于计算阶乘的算法。不幸的是，解释很简洁，我不想逐行筛选源代码来理解算法背后的基本原理。谁能告诉我这些(或其他快速的)计算阶乘的算法的更详细的描述？编辑： 描述了素数分解的方法，这是所有性能最好的阶乘算法共同使用的技术。它还包含一些用Python编写的很好的示例代码。作者链接到并引用了算法杂志上的一篇文...

问计算阶乘的快速算法
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算阶乘的快速算法EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算阶乘的快速算法
EN