C# 中的大整数



目前我正在从J#库中借用java.math.BigInteger,如此处所述。以前从未使用过库来处理大整数,这似乎很慢,慢了 10 倍,即使对于ulong长度的数字也是如此。有没有人有更好的(最好是免费)的库,或者这种性能水平是正常的吗?

从 .NET 4.0 开始,您可以使用 System.Numerics.BigInteger 类。 请参阅此处的文档:http://msdn.microsoft.com/en-us/library/system.numerics.biginteger(v=vs.110).aspx

另一种选择是 IntX 类。

IntX 是任意精度 用纯 C# 编写的整数库 2.0 使用快速 - O(N * log N) - 乘法/除法算法 实现。它提供了所有 对整数的基本操作,例如 加法、乘法、比较、 按位移位等。

F#也附带一个。你可以在 Microsoft.FSharp.Math .

.

NET 4.0 中的System.Numerics.BigInteger类基于 Microsoft Research 中的Microsoft.SolverFoundation.Common.BigInteger

求解器基金会的BigInteger类看起来非常高效。我不确定它是在哪个许可证下发布的,但你可以在这里获得它(下载并安装Solver Foundation并找到Microsoft.Solver.Foundation.dll)。

我认为,

如果您在 BigInts 上执行所有操作,这些操作将返回小于本机类型(例如 int64)的结果,并且仅在要溢出时处理大数组,则可以优化实现。

编辑代码项目上的这个实现,似乎只慢了 7 倍......但是通过上述优化,您可以使其与少量本机类型的性能几乎相同。

以下是 C# 中 BigInteger 的几种实现。我使用过Mono的BigInteger实现,工作速度非常快(我在CompactFramework中使用过它)

充气城堡

我不确定性能,但IronPython也有一个BigInteger类。 它位于 Microsoft.Scripting.Math 命名空间中。

是的,它会很慢,10 倍的差异大约是我所期望的。 BigInt 使用数组来表示任意长度,并且所有操作都必须手动完成(与可以直接使用 CPU 完成的大多数数学相反)

我什至不知道在汇编中手动编码是否会给您带来超过 10 倍的性能提升,这非常接近。 我会寻找其他方法来优化它 - 有时根据您的数学问题,您可以做一些小技巧来使其更快。

我在以前的工作中使用了Biginteger。 我不知道你有什么样的性能需求。 我没有在性能密集型情况下使用它,但从来没有遇到任何问题。

这听起来像是一个奇怪的建议,但是您是否测试了十进制类型以查看其工作速度?

十进制范围是 ±1.0 × 10^−28 到 ±7.9 × 10^28,所以它可能仍然不够大,但它比一个 ulong 大。

在.NET 3.5中应该有一个BigInteger类,但它被削减了。

这对你没有帮助,但是在.Net 3.5中应该有一个BigInteger类;它被削减了,但从PDC的声明来看,它将在.Net 4.0中。他们显然花了很多时间来优化它,所以性能应该比你现在得到的要好得多。

此外,这个问题本质上是 如何在 .NET 中表示非常大的整数?

查看此线程中的答案。你将需要使用可用的第三方大整数库/类之一,或者等待将包含本机 BigInteger 数据类型的 C# 4.0。

这看起来很有希望。它是GMP上的C#包装器。

http://web.rememberingemil.org/Projects/GnuMpDotNet/GnuMpDotNet.html

这里还有其他适用于 .Net 的 BigInteger 选项,Mpir.Net

你也可以

使用我写的Math.Gmp.Native Nuget包。它的源代码可在 GitHub 上找到,文档可在此处获得。它向 .NET 公开了 GMP 库的所有功能,该库被称为高度优化的任意精度算术库。

任意精度整数由 mpz_t 类型表示。对这些整数的操作都以 mpz_ 前缀开头。例如,mpz_add或mpz_cmp。给出了每个操作的源代码示例。

最新更新