Calculating the square of BigInteger

Question

Hi,

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

In practice how large do your numbers get? Why don't you just calculate the answers to your question empirically? This ought to be a great exercise in in real world you do care about actual numbers. Timing and averaging operations ought to be an easy task. What if your graphics card is utilized for these computations? See, you would probably never know until you tried. This probably should be a comment, but with 11 rep I am not allowed to comment yet. Please do not down-vote this one.

Answer 3

You can use a C# wrapper for GNU MP Bignum Library, which is probably as fast as you can get. For pure C# implementation you could try IntX.

Fastest multiplication algorithm is actually Fürer's algorithm, but I haven't found any implementations for it.

Answer 4

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.