计算BigInteger的平方

Question

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

我需要计算非常大的数字的平方(x ²) - 数百万的十进制数字.

如果x是a BigInteger,那么时间复杂度是多少:

x*x;

要么

BigInteger.Pow(x,2);

？

如何使用.NET 4 BigInteger以最快的方式增加这么大的数字？是否有Schönhage-Strassen算法的实现？

Answer 1

这取决于你的数字有多大.维基百科页面告诉您:

在实践中,Schönhage-Strassen算法开始优于旧方法,例如Karatsuba和Toom-Cook乘法,数字超过2 ^{2 15}到2 ^{2 17}(10,000到40,000十进制数字).

System.Numerics.BigInteger使用Karatsuba算法或标准教科书乘法,具体取决于数字的大小.Karatsuba的时间复杂度为O(n  ^{log ₂  3}).但如果你的数字小于上面引用的数字,那么你可能不会看到实施Schönhage-Strassen的速度加快.

至于Pow()这个数字在计算过程中至少将数字平方一次(并且它通过简单的方式来做num * num- 所以我认为这也不会更有效率.