Java library for fast multiplication of very big numbers

Question

I am writing a program which requires multiplication of very big numbers (million digit) at a point. Can anyone suggest a java library for a fast multiplication of big numbers? I have found this, but I'm not sure if this is the right solution, so I'm trying to find another to try.

Answer 1

The solution you link to — Schönhage-Strassen — is indeed a good way to make multiplying very very large BigIntegers faster.

Due to the big overhead, it is not faster for much smaller BigIntegers, so you can use this, recursively down to a certain threshold (you'll have to find out empirically what that theshold is) and then use BigInteger's own multiplication, which already implements the Toom-Cook and Karatsuba divide-and-conquer algorithms (since Java 8, IIRC), also recursively down to certain thresholds.

Forget the answers telling you to use Karatsuba. Not only does Java implement this already, as well as the even faster (for very large BigIntegers) Toom-Cook algorithm, it is also a lot slower (for such huge values) than Schönhage-Strassen.

Conclusion

Again: for small values, use simple schoolbook multiplication (but using – unsigned – integers as "digits" or "bigits"). For much larger values, use Karatsuba (which is a recursive algorithm, breaking large BigIntegers down to several smaller ones and multiplying these -- a divide-and-conquer algorithm). For even larger BigIntegers, use Toom-Cook (also a divide-and-conquer). For very large BigIntegers, use Schönhage-Strassen (IIRC, an FFT-based algorithm). Note that Java already implements schoolbook (or "base case"), Karatsuba and Toom-Cook multiplications, for differently sized Bigintegers. It does not implement Schönhage-Strassen yet.

But even with all these optimizations, multiplications of very huge values tend to be slow, so don't expect miracles.

---

Note:

The Schönhage-Strassen algorithm you link to reverts to Karatsuba for smaller sub-products. Instead of Karatsuba, revert to the, since then (Christmas day 2012), much improved implementation in BigInteger and simply use BigInteger::multiply() directly, instead of Karatsuba. You may also have to change the thresholds used.