3

こんにちは、最もタイムリーに最適化された方法で 2 つの大きな整数を乗算したいと考えています。私は現在カラツバアルゴリズムを使用しています。より最適化された方法やアルゴリズムを提案できますか?

ありがとう

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

4

複雑さと実際の速度は、実際には非常に異なるものです。これは、O 表記に含まれる一定の要因のためです。複雑さが優勢になる点は常にありますが、それは作業している (入力サイズの) 範囲外である可能性が非常に高いです。アルゴリズムの実装の詳細 (最適化のレベル) も、これらの定数要因に直接影響します。

私の提案は、いくつかの異なるアルゴリズムを試してみることです。できれば、作成者がすでに最適化にいくらかの労力を費やしているライブラリから、入力に対する速度を実際に測定して比較することをお勧めします。

SPOJ に関しては、主な問題が他の場所にある可能性を忘れないでください (つまり、大きな整数の乗算速度ではありません)。

于 2013-02-23T09:06:35.760 に答える