BigInteger.ModPow（）的替代品; 在C＃中

我正在寻找.NET 4.x引入的C＃BigInteger包的替代品。

使用这个对象的数学运算速度非常慢，我想这是因为算术是在比原始类型更高的层次上完成的 – 或者是非常优化的，无论如何。

Int64 / long / ulong或其他64位数字是小的，不会正确计算 – 我说的是64位整数到64位整数的幂。

希望有人可以建议我的东西。 提前致谢。

Answer 1

老实说，如果你有非常大的数字，需要用它们进行繁重的计算，并且BigInteger库仍然没有为你削减它，为什么不使用你知道的最好的语言或工具包将它卸载到外部进程上？ 您是否真的受限于编写您想要完全用C＃完成的任何内容？

例如，您可以在C＃中卸载到MATLAB 。

Answer 2

BIGInteger确实很慢。 其中一个原因是它的不变性。

如果您执行a = a – b，您将获得a的新副本。 通常这很快。 使用BigInteger并说一个2048位的整数，它将需要额外分配2KB。

它应该有不同的乘法算法，取决于整数（我认为它不是那么复杂）。 我的意思是，对于非常大的整数，使用傅里叶变换的不同算法效果最好，对于较小的整数，您可以用较小的乘法（分而治之的方法）来分解工作。 有关更多信息，请访问http://en.wikipedia.org/wiki/Multiplication_algorithm

无论哪种方式都有替代品，我没有使用或测试过。 对于我所知道的所有内容，它们可能比.NET内部更慢。 （制作测试用例并做一些有效的测试是你的朋友）

• 用于许多自制BigInteger实现的Google“C＃大整数乘法”（通常在引入BIGInteger时从C＃4.0开始）

• https://github.com/devoyster/IntXLib

• http://gmplib.org/ （有C＃包装器）

• http://www.extremeoptimization.com/ （商业）

• http://mathnetnumerics.codeplex.com/ （很好的开源，但对于非常大的整数而言，没有多少内容）

Answer 3

 public static int PowerBySquaring(int baseNumber, int exponent) { int result = 1; while (exponent != 0) { if ((exponent & 1)==1) { result *= baseNumber; } exponent >>= 1; baseNumber *= baseNumber; } return result; }