BigInteger时间最优乘法
BigInteger时间最优乘法
提问于 2013-02-23 16:36:14
嗨，我想在一个最及时的优化方式乘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));
}回答 2
Stack Overflow用户
回答已采纳
发布于 2013-11-18 07:18:00
jdk8中的BigInteger版本根据输入的大小在朴素算法、Toom-Cook算法和Karatsuba算法之间切换，以获得出色的性能。
Stack Overflow用户
发布于 2013-02-23 17:06:36
复杂性和实际速度在实践中是非常不同的东西，因为O表示法中涉及的恒定因素。总会有一个点，其中复杂性占主导地位，但它很可能超出了您正在处理的(输入大小)范围。算法的实现细节(优化程度)也直接影响这些恒定因素。
我的建议是尝试一些不同的算法，最好是来自作者已经花了一些精力优化的库，并实际测量和比较它们在输入上的速度。
关于SPOJ，不要忘记主要问题存在于其他地方(即不是大整数的乘法速度)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15038678
复制相关文章
相似问题
腾讯云开发者
