logo标签列表

在C#中处理非常大的整数

c#factorial
3

有没有人知道在 c# 中计算非常大的整数的方法？

我试图计算数字的阶乘，例如：

5! = 5*4*3*2*1 = 120

对于小数字来说，这不是问题，但试图计算无符号整数的最大值（4294967295）的阶乘似乎是不可能的。

我已经研究了 BigInteger 类，但它似乎不能满足我的需求。

任何帮助都将不胜感激。

1
阶乘的问题在于，即使在相对较小的整数（如256）上运行，它仍会产生大约507位数字的结果，因此我不敢想象4294967295！将产生多少位数字。浮点变量对我的应用程序没有用处。 - Avner
1
需要这样的应用程序是什么？听起来更像是计算机科学的家庭作业问题 :) - Matt Spradley
4
我还很好奇你需要精确值为2的32次方阶乘的用途。根据这个链接：http://www47.wolframalpha.com/input/?i=(2^32)!，其值约为10的39507966976次方。换句话说，这个数字比宇宙中大约10的80次方数量级的原子数量大约10的39507966896次方倍。 - Davy8
9个回答
10

要计算uint.MaxValue的阶乘，需要大量的存储空间。

例如，维基百科文章给出的结果为8.2639316883... × 10^5,565,708。你将会不断获取信息。

我强烈怀疑你不可能在一台正常的计算机上在合理的时间内计算出这个值。你需要这个值吗？使用斯特林公式近似计算是否足够精确？

我不认为任何近似值都能解决这个问题。首先，因为我需要精确的结果；其次，即使是一个近似值也仍然需要计算，并且仍然会是一个非常大的数字 - 对吧？ - Avner
这取决于你需要用它做什么。如果你可以将其保留为“大约是10的x次方”，其中x是某个数字，那么这比“确切地是1929494...”要少得多的信息。然而，如果你需要精确的结果，我怀疑你会遇到很大的问题。 - Jon Skeet
6
首先，有必要指出，uint.MaxValue 的阶乘是极大的。我无法找到其阶乘数量级的良好估计，但如果不超过标准RAM的高比例，其位表示可能会占用很高的百分比。
如果您只需要达到大约1,000,000左右（非常粗略），那么BigInteger类似乎是您想要的。在当前（稳定）版本的.NET中，直到3.5，您必须使用自定义实现。CodeProject上的这个实现似乎评价很高。如果您正在开发.NET 4.0，则微软团队终于开始在BCL的System.Numerics命名空间中包含一个BigInteger类。与一些BigInteger实现不同，存在于.NET 4.0中的实现没有内置的阶乘方法（我不确定CodeProject的实现如何），但是实现一个该方法应该很容易——扩展方法是一种好方式。
由于您似乎认为不想使用BigInteger类型，请在阅读我的回复后验证它是否适合您的目的，并解释为什么不适合您的目的。
它在2.0 beta版本中存在，但在最终版本中被移除了... 那时它是System.Numeric.BigInteger，我希望他们这次不要改变主意... - Mehrdad Afshari
是的，我确实对.NET开发人员有很大的信心。 :) 或许我只是太乐观了...文档已经编写完成这一事实只能是个好兆头。 - Noldorin
1
是的，可能他们撤下了它，以便在v4.0中添加更多不仅仅是“动态”的东西。开个玩笑。 - Mehrdad Afshari
Noldorin - 并不是我不想使用 BigInteger 类 - 我已经尝试过了 - 但在某个时候我一直收到一个异常。有一个叫做 maxLength 的设置必须被改变，但无论我将其设置为什么值 - 当我在大数上运行它时，它仍然会抛出异常。我想我只能继续努力解决它 - 谢谢！ - Avner
Noldorin - 是的，我是 - 再次感谢 - Avner
显示剩余3条评论
5

4294967295! = 10^(10^10.597) ~ 10^(40000000000)。即使你能找到任何C#的BigInteger实现，这个值需要大约40 Gb的RAM来存储。

另外，如果采用优化的存储方式，比如说4字节存储9位数字，那么需要大约18 Gb的RAM。

1
我能理解你的观点。我想在目前的技术条件下，这不是实际可行的。谢谢。 - Avner
嘿，伙计们，你们的讨论完全不是数学的 :) 我们需要基于伽玛函数的任意精度数字的阶乘。不要一个蠢到爆炸的递归函数。有很多这样的函数，但我还没有在C#中找到一个。 - Harry
2
为什么您认为需要计算这些阶乘呢？实际上，对于任何实际计算来说，这都没有什么用处。
仅计算(2^32-1)的阶乘结果就会占用大量空间，约为16 GB。
当然，计算本身也需要很长时间。如果您构建程序，使其能够随着更快硬件的发明而将计算过程转移到更快的硬件上，您应该能够在有生之年得出结果。
如果您试图解决类似于Euler问题的问题，请考虑通过消除不必要的计算来获得答案，因为许多解决方案都是通过这种方式找到的。
1

这里。 最快的方法，直接来自阶乘专家Peter Luschny。

0
尝试使用数组来完成这个任务。您可以使用尽可能长的整数，只要有足够的内存空间。数组的每个成员代表一个十进制数字。您所需要做的就是实现乘法运算。
你有没有实现你所描述的基本代码？当你说数组的每个成员都代表一个十进制数字时，这不会浪费空间吗？因为即使我有一个字节数组，每个字节也只能容纳一个数字，而实际上它可以容纳高达255的值。除非我没有理解你的意思？！ - Avner
我意识到这与创建新的整数类型类似。您需要实现基本操作，例如乘法。将1个十进制数字存储到字节中可能会浪费空间。但是，您可以使用位数组（例如BitArray类）。 这里有一些基本代码http://www.daniweb.com/code/snippet233.html 希望能有所帮助。 - Vanuan
0
0
如果您已安装了J# redist，另一种方法是通过添加对vjslib程序集的引用来使用java.math.BigInteger。
0

如果你正在进行阶乘计算，例如组合，你很少需要一直乘到1（例如98 * 98 * 97，因为其他所有数都会被消除）。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接