3

嗨，我想以最及时优化的方式将 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));
    }
4

2 回答 2

7

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

于 2013-11-17T23:17:59.567 回答
4

由于 O 符号中涉及的常数因素，复杂性和实际速度在实践中是非常不同的事情。总有一点复杂性占主导地位，但它很可能超出您正在使用的（输入大小）范围。算法的实现细节（优化级别）也直接影响这些常数因素。

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

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

于 2013-02-23T09:06:35.760 回答