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.

Answer 2

As far as my thinking abilities the Karatsuba Algorithm can be implemented in this manner:

This link provides with a C++ implementation of the same, this can be easily adopted for the Java like implementation easily as well.

import java.math.BigInteger;
import java.util.Random;

class Karatsuba {
    private final static BigInteger ZERO = new BigInteger("0");

    public static BigInteger karatsuba(BigInteger x, BigInteger y) {

        // cutoff to brute force
        int N = Math.max(x.bitLength(), y.bitLength());
        if (N <= 2000) return x.multiply(y);                // optimize this parameter

        // number of bits divided by 2, rounded up
        N = (N / 2) + (N % 2);

        // x = a + 2^N b,   y = c + 2^N d
        BigInteger b = x.shiftRight(N);
        BigInteger a = x.subtract(b.shiftLeft(N));
        BigInteger d = y.shiftRight(N);
        BigInteger c = y.subtract(d.shiftLeft(N));

        // compute sub-expressions
        BigInteger ac    = karatsuba(a, c);
        BigInteger bd    = karatsuba(b, d);
        BigInteger abcd  = karatsuba(a.add(b), c.add(d));

        return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N)).add(bd.shiftLeft(2*N));
    }


    public static void main(String[] args) {
        long start, stop, elapsed;
        Random random = new Random();
        int N = Integer.parseInt(args[0]);
        BigInteger a = new BigInteger(N, random);
        BigInteger b = new BigInteger(N, random);

        start = System.currentTimeMillis(); 
        BigInteger c = karatsuba(a, b);
        stop = System.currentTimeMillis();
        StdOut.println(stop - start);

        start = System.currentTimeMillis(); 
        BigInteger d = a.multiply(b);
        stop = System.currentTimeMillis();
        StdOut.println(stop - start);

        StdOut.println((c.equals(d)));
    }
}

Hope this answers your question well.