BigInteger optimizes multiplication times

Question

Hi, I want to multiply 2 large integers in the most timely optimized way. I am currently using the karatsuba algorithm. Can anyone suggest a more optimized way or algo to do this.

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 BigInteger version 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

The complexity and actual speed are very different in practice, due to the constant factors associated with the O designation. There is always a point where complexity prevails, but it may well be outside the range (input size) with which you work. Implementation details (optimization level) of the algorithm also directly affect these constant factors.

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

As for SPOJ, do not forget that the main problem lies elsewhere (i.e. not in the rate of multiplication of large integers).