BigInteger mais tempo otimizado multiplicação

Oi eu quero multiplicar 2 inteiro grande de uma forma otimizada mais oportuna. Atualmente estou usando o algoritmo karatsuba. Alguém pode sugerir uma maneira mais otimizada ou algo para fazê-lo.

obrigado

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)); } 

A versão do BigInteger no jdk8 alterna entre o algoritmo ingênuo, o algoritmo Toom-Cook e o Karatsuba, dependendo do tamanho da input para obter um excelente desempenho.

Complexidade e velocidade real são coisas muito diferentes na prática, por causa dos constantes fatores envolvidos na notação de O. Há sempre um ponto em que a complexidade prevalece, mas pode muito bem estar fora do intervalo (de tamanho de input) com o qual você está trabalhando. Os detalhes da implementação (nível de otimização) de um algoritmo também afetam diretamente esses fatores constantes.

Minha sugestão é tentar alguns algoritmos diferentes, preferencialmente de uma biblioteca, que os autores já tenham gasto algum esforço para otimizar, e realmente medir e comparar suas velocidades em suas inputs.

Em relação ao SPOJ, não esqueça a possibilidade de que o principal problema esteja em outro lugar (isto é, não na velocidade de multiplicação de inteiros grandes).