c# - 计算 BigInteger 的平方

Question

我正在使用 .NET 4 的 System.Numerics.BigInteger structure .

我需要计算非常大的数的平方 (x²) - 数百万位小数。

如果x是一个BigInteger，那么时间复杂度是多少:

x*x;

或

BigInteger.Pow(x,2);

?

如何使用 .NET 4 BigInteger 以最快的方式乘以如此大的数字？是否有 Schönhage–Strassen algorithm 的实现？ ？

Answer 1

这取决于您的数字有多大。正如维基百科页面告诉您的那样:

In practice the Schönhage–Strassen algorithm starts to outperform older methods such as Karatsuba and Toom–Cook multiplication for numbers beyond 2²¹⁵ to 2²¹⁷ (10,000 to 40,000 decimal digits).

System.Numerics.BigInteger 使用 Karatsuba algorithm或标准教科书乘法，取决于数字的大小。 Karatsuba 的时间复杂度为 O(n ^{log₂ 3})。但是，如果您的数字小于上面引用的数字，那么您可能不会从实现 Schönhage–Strassen 中看到太多加速。

至于 Pow() 这本身在计算期间至少对数字进行一次平方(它通过简单地执行 num * num 来做到这一点——所以我认为这赢了也更有效率。