BigInteger大部分时间都是优化乘法

嗨我想以最及时优化的方式乘以2大整数。 我目前正在使用karatsuba算法。 任何人都可以建议更优化的方式或算法来做到这一点。

谢谢

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

jdk8中的BigInteger版本在朴素算法，Toom-Cook算法和Karatsuba之间切换，具体取决于输入的大小，以获得出色的性能。

Answer 2

复杂性和实际速度在实践中是非常不同的，因为O符号中涉及的常数因素。 始终存在复杂性占优势的点，但它可能超出您正在使用的范围（输入大小）。 算法的实现细节（优化级别）也直接影响那些常数因子。

我的建议是尝试一些不同的算法，最好是从作者已经花费一些精力优化的库，并实际测量和比较他们的输入速度。

关于SPOJ，不要忘记主要问题存在于其他地方的可能性（即不是大整数的乘法速度）。