Calculating the square of BigInteger

Question

I'm using .NET 4's System.Numerics.BigInteger structure.

I need to calculate the square (x²) of very large numbers - millions of decimal digits.

If x is a BigInteger, What is the time complexity of:

x*x;

or

BigInteger.Pow(x,2);

?

How can multiply such big numbers in the fastest way using .NET 4 BigInteger? Is there an implementation for Schönhage–Strassen algorithm?

Answer 1

That depends on how large your numbers are. As the Wikipedia page tells you:

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 uses the Karatsuba algorithm or standard schoolbook multiplication, depending on the size of the numbers. Karatsuba has a time complexity of O(n ^log₂ 3). But if your numbers are smaller than above quoted figures, then you likely won't see much speedup from implementing Schönhage–Strassen.

As for Pow() this itself squares the number at least once during its calculations (and it does that by simply doing num * num – so I think this won't be more efficient, either.

Answer 2

There is a Schönhage-Strassen implementation here:

https://github.com/tbuktu/ntru/blob/master/src/main/java/net/sf/ntru/arith/Sch%C3%B6nhageStrassen.java

Answer 3

A quite simple method to implement is based on FFT. Since multiplying two numbers amounts to perform a convolution of their coefficients followed by a pass to eliminate carries, you should be able to do the convolution in O(n log n) operations via FFT methods (n = number of digits).

Numerical recipes has a chapter on this. This is definitely faster than divide and conquer methods, like Karatsuba, for such big numbers.