BigInteger的大部分时间优化乘法(BigInteger most time optimize

您好我想乘以最及时的方式优化的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:

BigInteger的天真的算法，南通，库克的算法，Karatsuba之间jdk8开关取决于输入的大小的版本，以获得卓越的性能。

Answer 2:

复杂性和实际速度在实践中是非常不同的事情，因为参与O符号常量因素。 总是有地方盛行的复杂点，但它很可能出你正在使用的（输入大小）的范围。 算法的实现细节（优化级）也直接影响这些常数因子。

我的建议是尝试一些不同的算法，优选的是，作者已经花了一些力气优化库，并实际测量，并在您输入比较它们的速度。

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

文章来源: BigInteger most time optimized multiplication