计算C#中的阶乘

Question

如何使用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

也许这可以帮助您实现此功能.

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的算法,例如,您可以为任意大的整数执行渐近快速乘法.

例如,Mathematica22000!在不到1秒的时间内在我的机器上进行计算.reference.wolfram.com上的Implementation Notes页面指​​出:

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

不幸的是,这种算法的实现既复杂又容易出错.您可以更明智地许可Mathematica(或满足您的功能和性能需求的类似产品)的副本,并使用它或.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;
}

将被计算为

124101807021766782342484052410310399261660557750169318538895180361199607522169175299275197812048758557646495950167038705280 98898586907107673312420322184843643104735778899685482782907545415619648521534683180442932395981736968996572359039476161522785 58180061176365108428800000000000000000000000000000000000000000

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