BigInteger most time optimized multiplication

Question

Hi I want to multiply 2 big integer in a most timely optimized way. I am currently using karatsuba algorithm. Can anyone suggest more optimized way or algo to do it.

Thanks

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

        // cutoff to brute force
        int N = Math.max(x.bitLength(), y.bitLength());
        System.out.println(N);
        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));
    }

Answer 1

The version of BigInteger in jdk8 switches between the naive algorithm, The Toom-Cook algorithm, and Karatsuba depending on the size of the input to get excellent performance.

Answer 2

Complexity and actual speed are very different things in practice, because of the constant factors involved in the O notation. There is always a point where complexity prevails, but it may very well be out of the range (of input size) you are working with. The implementation details (level of optimization) of an algorithm also directly affect those constant factors.

My suggestion is to try a few different algorithms, preferably from a library that the authors already spent some effort optimizing, and actually measure and compare their speeds on your inputs.

Regarding SPOJ, don't forget the possibility that the main problem lies elsewhere (i.e. not in the multiplication speed of large integers).