1

3 つの等間隔のものを見つけることに関する最近のパズル ブログ投稿は、O(n lg n) 時間でそれを行うと主張するトップの回答を持つスタック オーバーフローの質問に私を導きます。興味深いのは、O(n lg n) 時間でそれを行う方法を説明している論文を参照して、解決策に多項式の 2 乗が含まれていることです。

さて、多項式の掛け算は実際には数の掛け算と同じです。唯一の本当の違いは、キャリーの欠如です。しかし...キャリーはO(n lg n)時間で行うこともできます。例えば：

    var value = 100; // = 0b1100100

    var inputBitCount = value.BitCount(); // 7 (because 2^7 > 100 >= 2^6)
    var n = inputBitCount * 2; // 14
    var lgn = n.BitCount(); // 4 (because 2^4 > 14 => 2^3)
    var c = lgn + 1; //5; enough space for 2n carries without overflowing

    // do apparently O(n log n) polynomial multiplication
    var p = ToPolynomialWhereBitsAreCoefficients(value); // x^6 + x^5 + x^2
    var p2 = SquarePolynomialInNLogNUsingFFT(p); // x^12 + 2x^11 + 2x^10 + x^8 + 2x^7 + x^4
    var s = CoefficientsOfPolynomial(p2); // [0,0,0,0,1,0,0,2,1,0,2,2,1]
    // note: s takes O(n lg n) space to store (each value requires at most c-1 bits)

    // propagate carries in O(n c) = O(n lg n) time
    for (var i = 0; i < n; i++)
        for (var j = 1; j < c; j++)
            if (s[i].Bit(j))
                s[i + j].IncrementInPlace();

    // extract bits of result (in little endian order)
    var r = new bool[n];
    for (var i = 0; i < n; i++)
        r[i] = s[i].Bit(0);

    // r encodes 0b10011100010000 = 10000

だから私の質問はこれです: ここで間違いはどこですか? O(n lg n) で数を乗算することは、コンピューター サイエンスにおける巨大な未解決の問題であり、答えがこれほど単純であるとは本当に思えません。

  • 持ち方が悪いのか、O(n lg n) でないのか？キャリーを追跡するには、値ごとに lg n + 1 ビットで十分であることがわかりました。アルゴリズムは非常に単純なので、間違っていたら驚くでしょう。個々のインクリメントには O(lg n) の時間がかかる場合がありますが、x 個のインクリメントの総コストは O(x) であることに注意してください。
  • 論文の多項式乗算アルゴリズムは間違っていますか、それとも私が違反している条件がありますか? この論文では、数論的変換の代わりに高速フーリエ変換を使用していますが、これが問題になる可能性があります。
  • シェーンハーゲ・シュトラッセン アルゴリズムの明らかな変種を 40 年間、多くの賢い人々が見逃していたのでしょうか? これは、最も可能性が低いようです。

効率的な多項式の乗算を除いて、実際にこれを実装するコードを作成しました (数論変換はまだ十分に理解していません)。ランダム テストでは、アルゴリズムが正しいことを確認しているように見えるため、問題は時間の複雑さの分析にある可能性があります。

4

1 に答える 1

3

問題は、SquarePolynomialUsingFFTn がワード RAM またはビット RAM モデルのビット数である場合、O(n log(n)) 時間で実際にステップを実行できないことです。ワード RAM モデル (つまり、log(n) ビット ワードの一般的な操作には単位コストがあります) では、n ワードを n log(n) ワードに吹き飛ばしてから、O(n log の FFT を実行します。2 (n)) 時間。ビット RAM モデル (ビット操作には単位コストがあります) では、FFT の各操作に O(log n) の時間がかかるため、FFT 全体では O(n log 2 (n)) の時間がかかります。

Schoenhage-Strassen の魔法は、リングの巧妙な再帰的選択であり、FFT が取得されるため、さらに log(n) ブローアップが発生せず、log(log(n)) ブローアップのみが取得されます。k 個の m ワード リング要素 (k*m = n) がある場合、そのリングで m FFT を実行するのに O(m*k log(k)) 時間しか必要ありません。次に、これを行う場合、k^2 関連の m-word 畳み込みを計算する必要がありますが、それは素晴らしいことです。m ワード リング要素のすべての k をまとめて FFT (より小さなリングを使用) し、乗算を行い、逆 FFT で戻すことができます。

于 2013-01-19T05:22:50.863 に答える