计算C中的阶乘#

看看 BigInteger 结构:

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

也许这可以帮助你实现这个功能。

CodeProject在 http://www.codeproject.com/KB/cs/biginteger.aspx .

如果我尝试用C#[递归或循环]编写一个简单的阶乘代码,那么性能真的很差。需要几秒钟才能得到答案。

让我们在这里为执行n个乘法的阶乘的朴素实现做一个快速的数量级计算。假设我们走到了最后一步。19999年!大约是2 ^18岁 位。2万左右 ^5个 位;我们假设它是一个32位整数。因此,最后的乘法运算需要2的加法运算 ^5个 部分结果各约2 ^18岁 有点长。因此,位操作的数量大约为2 ^23个 .

这是最后一个阶段;将有20000=2 ^16个 这样的操作在每个阶段,所以总共大约有2个 ^39个 操作。其中一些当然会便宜一些,但我们这里的价格是一个数量级。

现代的处理器大约有2个 ^32个 每秒操作数。因此大约需要2 ^7个 几秒钟后得到结果。

当然,大整数库的编写者并不幼稚;他们利用芯片的能力并行执行许多位操作。他们可能是32位的一组,给出了2倍的加速比 ^5个 . 所以我们的总数量级计算是 ^2个 几秒钟就能得到结果。

2个 ^2个 是4。所以你的观察结果需要几秒钟才能得到。

Windows 2k3(或XP)中的calc如何能够在不到10秒的时间内执行如此大的阶乘运算?

我不知道。利用芯片上的数学运算可能非常聪明。或者,使用非朴素算法计算阶乘。或者,他们可能是使用斯特灵的近似,得到一个不精确的结果。

在C#中有没有其他的编程计算阶乘的方法?

当然。如果你关心的是数量级,那么你可以使用斯特灵的近似值。如果你关心确切的值,那么你就必须计算它。

存在复杂的计算算法,用于有效地计算大、任意精度数的阶乘。 这个 Schönhage–Strassen algorithm 例如,允许对任意大整数执行渐近快速乘法。

举个例子, Mathematica 计算 22000! 在我的机器上不到一秒钟。这个 Implementation Notes reference.wolfram.com上的页面说明:

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

不幸的是,这种算法的实现既复杂又容易出错。 与其尝试滚动自己的实现,不如授权Mathematica的副本(或满足功能和性能需求的类似产品)并使用它,或者 .NET programming interface 为了它,为了执行你的计算。

你看过吗 System.Numerics.BigInteger ?

使用系统数字 BigInteger

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

将计算为

124101807021766782344840524103992616605577501693185388895180361199607522169299275197812048755764950167038705280988980710767331242032218436431047357788996852782907541561964852153468344293239598173696572356152785861176510842880000000000000000000000000000000000000000000000000000000

五万块!它需要几秒钟的时间来计算,但似乎是可行的,结果是一个213237位的数字,这也是 Wolfram 说。

您可能需要实现自己的任意精度数值类型。

有各种方法。可能不是最有效的方法,但最简单的方法是使用可变长度的字节数组(无符号字符)。每个元素代表一个数字。理想情况下,这将包含在一个类中,然后您可以添加一个方法,让您将该数字与另一个任意精度的数字相乘。使用标准C#整数乘法可能也是一个好主意,但实现起来要复杂一些。

你需要一个特殊的大数字库。 This link 介绍了System.Numeric.BigInteger类,附带有一个计算阶乘的示例程序。但不要用这个例子!如果你像那样递归,你的堆栈将可怕地增长。只要写一个for循环就可以完成乘法运算。

因为他们没有把结果归结到最后一个数字,所以他们可能会用一些近似来“作弊”。 退房 http://mathworld.wolfram.com/StirlingsApproximation.html 使用斯特灵公式,你可以计算(近似)n在对数时间内的阶乘。当然,他们也可以有一个字典,预先计算出每n的阶乘(n)值,最大可达一百万,使计算器显示结果非常快。

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

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

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

内置数字类型的限制:

• short -最多7个正确结果!,之后的结果不正确,代码从18开始返回0(类似于int)
• int -最多12个正确结果!,之后的结果不正确,代码从34开始返回0( Why computing factorial of realtively small numbers (34+) returns 0 )
• float -精确的结果高达14!,正确但不精确,返回从35开始的无穷大
• long -正确结果最多20个!,之后的结果不正确,代码从66开始返回0(类似于 内景 )
• double -精确到22!,正确但不精确,返回从171开始的无穷大
• BigInteger -精确和上限仅由内存使用量设置。

注意:整数类型很快就会溢出,并开始产生不正确的结果。如果你需要阶乘的话 长的 是要使用的类型(最多20!),如果你不能期望有限的数量- 大整数 是.Net Framework中提供的唯一提供精确结果的类型(尽管对于大量数据来说速度很慢,因为没有内置的优化n!方法)

我不知道你怎么能用一种没有任意精确算法的语言做到这一点。我想一个开始可能是计算5和2的因子,从产品中去掉它们,然后在最后加上这些零。

你可以看到有很多。

>>> factorial(20000)
<<non-zeroes removed>>0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L