计算C＃中的阶乘

如何使用C＃计算大因子？ Win 7中的Windows计算器在Factorial（3500）中溢出。 作为编程和数学问题，我有兴趣知道如何在C＃中计算更大数（20000，可能）的阶乘。 有什么指针吗？

[编辑]我刚刚在Win 2k3上使用了一个计算结果，因为我记得在Win 2k3上做了一个更大的因子。 事情发展的方式令我感到惊讶。

1. Win2k3上的Calc甚至可以处理大数字。 我试过了！50000我得到了答案，3.3473205095971448369154760940715e + 213236

2. 我这么做的时候速度非常快。

这里的主要问题不仅是找出适当的数据类型，还要有点数学。 如果我尝试在C＃[递归或循环]中编写一个简单的因子代码，性能真的很糟糕。 获得答案需要几秒钟。 Windows 2k3（或XP）中的计算如何在不到10秒的时间内执行如此巨大的因子？ 有没有其他方法在C＃中以编程方式计算factorial？

Answer 1

看看BigInteger结构：

http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.aspx

也许这可以帮助您实现此function。

CodeProject在http://www.codeproject.com/KB/cs/biginteger.aspx上有一个旧版本框架的实现。

Answer 2

如果我尝试在C＃[递归或循环]中编写一个简单的因子代码，性能真的很糟糕。 获得答案需要几秒钟。

让我们在这里进行一个快速的数量级计算，以实现执行n次乘法的阶乘的简单实现。 假设我们是最后一步。 19999！ 约为2 ¹⁸位。 20000约为2 ⁵位; 我们假设它是一个32位整数。 因此，最终的乘法包括添加多达2 ^5个部分结果，每个结果大约为2 ¹⁸位长。 因此，位操作的数量将为2 ²³ 。

那是最后一个阶段; 每个阶段将有20000 = 2 ^16个此类操作，因此总共约有2 ^39个操作。 其中一些当然会更便宜，但我们在这里要达到一个数量级。

现代处理器每秒执行大约2 ^32次操作。 因此，获得结果大约需要²⁷秒。

当然，大整数图书馆作家并不天真; 他们利用芯片的能力并行进行多个位操作。 他们可能在32位块中进行数学计算，加速度为2 ⁵ 。 因此，我们的总数量级计算是需要大约2 ²秒才能得到结果。

2 ²是4.因此，您的观察结果需要几秒钟才能得到结果。

Windows 2k3（或XP）中的计算如何在不到10秒的时间内执行如此巨大的因子？

我不知道。 可能在利用芯片上的数学运算时极为聪明。 或者，使用非天真算法计算阶乘。 或者，他们可能正在使用斯特林的近似并得到一个不精确的结果。

有没有其他方法在C＃中以编程方式计算factorial？

当然。 如果您关心的只是数量级，那么您可以使用斯特林的近似值。 如果您关心确切的值，那么您将不得不计算它。

Answer 3

存在用于有效计算大的任意精度数的阶乘的复杂计算算法。 例如， Schönhage-Strassen算法允许您对任意大整数执行渐近快速乘法。

例如， Mathematica计算22000! 在我的机器上不到1秒钟。 reference.wolfram.com上的Implementation Notes页面指​​出：

(Mathematica's) n! uses an (Mathematica's) n! uses an algorithm of Schönhage based on dynamic decomposition to prime powers. (Mathematica's) n! uses an O(log(n) M(n)) algorithm of Schönhage based on dynamic decomposition to prime powers.

不幸的是，这种算法的实现既复杂又容易出错。 您可以更明智地许可Mathematica（或满足您的function和性能需求的类似产品）的副本，并使用它或.NET编程接口来执行它，而不是尝试推出自己的实现。你的计算。

Answer 4

你看过System.Numerics.BigInteger吗？

Answer 5

使用System.Numerics BigInteger

 var bi = new BigInteger(1); var factorial = 171; for (var i = 1; i <= factorial; i++) { bi *= i; } 

将计算到

1241018070217667823424840524103103992616605577501693185388951803611996075221691752992751978120487585576464959501670387052809889858690710767331242032218484364310473577889968548278290754541561964852153468318044293239598173696899657235903947616152278558180061176365108428800000000000000000000000000000000000000000

50000！ 计算需要几秒钟，但它似乎有效，结果是一个213237的数字，这也是Wolfram所说的。

Answer 6

您可能必须实现自己的任意精度数字类型。

有各种方法。 可能不是最有效的，但也许最简单的是拥有可变长度的byte（unsigned char）数组。 每个元素代表一个数字。 理想情况下，这将包含在一个类中，然后您可以添加一个方法，让您将该数字与另一个任意精度数相乘。 与标准C＃整数相乘可能也是一个好主意，但实现起来有点棘手。

Answer 7

你需要一个特殊的大号库。 此链接介绍了System.Numeric.BigInteger类，并且顺便提供了一个计算阶乘的示例程序。 但是不要使用这个例子！ 如果你像这样递归，你的筹码将会变得非常可怕。 只需编写一个for循环来进行乘法运算。

Answer 8

由于他们没有将结果提供给最后一位数字，因此他们可能会使用某种近似值“作弊”。 查看http://mathworld.wolfram.com/StirlingsApproximation.html使用斯特林公式，您可以计算（近似值）登录时间中的n的阶乘。 当然，它们也可能有一个字典，其中每n个高达一百万的阶乘（n）的预先计算值，使计算器显示结果非常快。

Answer 9

这个答案涵盖了计算和表示n的基本.Net类型的限制！

计算支持乘法的“SomeType”的阶乘的基本代码：

 SomeType factorial = 1; int n = 35; for (int i = 1; i <= n; i++) { factorial *= i; } 

内置数字类型的限制：

• short - 正确的结果最多7！，之后结果不正确，代码返回0开始18（类似于int）
• int - 将结果更正为12！，之后结果不正确，代码从34开始返回0（ 为什么计算小数（34+）的因子返回0 ）
• float - 精确的结果，最多14个！，之后正确但不精确，从35开始返回无穷大
• long - 正确结果，最多20个！，之后结果不正确，代码从66开始返回0（类似于int ）
• double - 精确结果，最多22个！，之后正确但不精确，从171开始返回无穷大
• BigInteger - 精确和上限仅由内存使用量设置。

注意：整数类型很快溢出并开始产生不正确的结果。 实际上，如果你需要任何实际用法的阶乘，那就是要去的类型（最多20个！），如果你不能指望有限的数字 - BigInteger是.Net Framework中提供的唯一类型，以提供精确的结果（虽然大而且很慢）数字，因为没有内置优化的n！方法）

Answer 10

我不知道你怎么能用没有任意精度算术的语言来做这件事。 我想一个开始可能是计算因子5和2，从产品中删除它们，并在最后加上这些零。

你可以看到有很多。

 >>> factorial(20000) <>