java 获得大数的阶乘
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/10148115/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Getting factorial of a large number
提问by Ravi Joshi
Possible Duplicate:
Calculate the factorial of an arbitrarily large number, showing all the digits
可能的重复：
计算任意大数的阶乘，显示所有数字
This question might be asked thousand times here. I am repeating my question with a modification. I want to calculate factorial of a large number (max range of the number=10^6). Generally we uses a forloop from i=1to i=numberand every time multiplying the old value to the new value. This is fine for small numbers but what if i have a large number? The range of forloop is increased now. Java primitive data type int, longcan't handle the resultant large number. They simply overflows. Although i knew about BigIntegerclass, which can handle this large output but still forloop is not suiting better here for me. Can somebody please suggest me any tick, any hack to calculate factorial of a number? Below is the simple program which works fine for small number-
这个问题在这里可能会被问一千次。我正在通过修改重复我的问题。我想计算一个大数 ( max range of the number=10^6) 的阶乘。通常我们使用for循环 from i=1toi=number和每次将旧值乘以新值。这对小数字很好，但如果我有大数字怎么办？for现在循环的范围增加了。Java 原始数据类型int，long无法处理由此产生的大量数据。他们只是溢出。虽然我知道BigIntegerclass，它可以处理这么大的输出，但仍然for循环不适合我。有人可以建议我任何勾号，任何计算数字阶乘的技巧吗？以下是适用于少量的简单程序-
public long getFactorial(long number) {
long factorial = 1;
for (long i = 1; i <= number; ++i) {
factorial *= i;
}
return factorial;
}
回答by Louis Wasserman
Understand that the value is in the range of 105565708. It's going to take up about two megabytes of space, all by itself.
了解该值在 10 5565708的范围内。它将单独占用大约 2 兆字节的空间。
That said, Guava'sBigIntegerMath.factorial(int)is good enough to handle it, and more importantly, it's actually been optimized for large factorials -- it'll do significantlybetter than a straightforward forloop. (Disclosure: I contribute to Guava...and wrote much of BigIntegerMath.factorialmyself.)
这就是说，番石榴的BigIntegerMath.factorial(int)好足以应付它，更重要的是，它实际上是为大阶乘优化-它会做显著比一个简单的好for环。（披露：我为 Guava 做出了贡献……并且写了很多BigIntegerMath.factorial我自己的文章。）
That said, I wouldn't exactly call it fast -- my benchmarks indicate an average of 414ms for a factorial in that range -- but there isn't going to be a truly fast solution, not without extremely heavy-duty bignum libraries, and I wouldn't expect even those to be significantlyfaster.
也就是说，我不会完全称之为快速——我的基准测试表明该范围内的阶乘平均为 414 毫秒——但不会有真正快速的解决方案，除非没有极其重型的 bignum 库，我不希望即使是那些会明显更快。
That's if you need the exact value. If you can settle for the logarithm, then yeah, either use Apache's logGamma(n+1)to get ln(n!), or approximate it yourself:
那就是如果您需要确切的值。如果你能满足于对数，那么是的，要么使用 Apache'slogGamma(n+1)来获取ln(n!)，要么自己近似：
double logFactorial = 0;
for (int i = 2; i <= n; i++) {
logFactorial += Math.log(i);
}
Some rounding error will probably accumulate, but it's supposed to be an approximation anyway.
一些舍入误差可能会累积，但无论如何它应该是一个近似值。
回答by Hunter McMillen
You can use an approximation function called Stirling's Formulafor such large values of n.
对于如此大的 n 值，您可以使用称为斯特林公式的近似函数。
You can refer to my answer here for more details: https://softwareengineering.stackexchange.com/questions/134968/number-of-combinations/134972#134972
您可以在此处参考我的回答以获取更多详细信息：https: //softwareengineering.stackexchange.com/questions/134968/number-of-combinations/134972#134972
回答by j13r
Use the Gamma function. Gamma(i + 1) = i!
使用Gamma 函数。伽玛(i + 1) = i！
org.apache.commons.math.specialprovides it for Java.
org.apache.commons.math.special为 Java 提供了它。
What people typically do is to calculate log(Gamma(i+1)) and then work in log-space (multiplications become additions, etc.).
人们通常做的是计算 log(Gamma(i+1)) 然后在对数空间中工作（乘法变成加法等）。
Here are some other methods to calculate the factorial quickly: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
以下是一些其他快速计算阶乘的方法：http: //www.luschny.de/math/factorial/FastFactorialFunctions.htm
回答by Ned Batchelder
You use BigIntegerfor factorial, and you still only need a longfor i, the loop variable. ionly has to go up to 1000000. What's the problem?
您使用BigIntegerforfactorial并且您仍然只需要一个longfori循环变量。 i只需要涨到1000000。有什么问题？
