您好我想以最及时的优化方式乘以2个大整数。我目前使用karatsuba算法。任何人都可以提出更优化的方法或算法来做到这一点。BigInteger大部分时间优化乘法
感谢
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));
}
BigInteger.Multiply()有什么问题? – 2013-02-23 08:38:04
它的复杂性是O(n^2)的次序。 Karatsuba约为O(n^1.5)。我想要一个更优化的。 – KingJames 2013-02-23 08:39:34
如果你想要速度,那为什么不尝试Toom-Cook? – 2013-02-23 08:48:30