BigInteger most time optimized multiplication
algorithm, biginteger, java, multiplication, performance
Solution
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.
Problem
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)); } ```