2

高速 GCD 計算アルゴリズムに関する情報を探しています。特に、その実現に注目したい。

私にとって最も興味深いもの: - Lehmer GCD アルゴリズム - Accelerated GCD アルゴリズム - k-ary アルゴリズム - FFT を使用した Knuth-Schonhage。高速化された GCD アルゴリズムに関する情報はまったくありません。中程度の入力 (〜 1000 ビット) で最も効果的で高速な gcd 計算方法として言及されている記事をいくつか見ただけです。

理論的な観点からは、それらを理解するのは非常に難しいように見えます。リストからアルゴリズム\パーツを実現したコード（C ++で望ましい）を共有するか、これを行った経験を共有してください。また、情報、コメント、アドバイス、調べるべき場所を教えていただければ幸いです。大きな整数を扱うクラスがありますが、それを扱うメソッドがありません。確かに、Euclid と Binary gcd アルゴリズムを除いて、今のところ私には明らかです。問題ありません。私が最後に取得したい主なもの: 実現のコード lehmer gcd. （リストのほうが簡単です）

4

2 に答える 2

6

Knuth は、The Art of Computer Programming、第 2 巻、セクション 4.5.2 で GCD について詳しく説明しています。Knuth は、アルゴリズム E をユークリッドの元の方法として、アルゴリズム A をユークリッドのアルゴリズムの現代版として、アルゴリズム B を 2 進法として、アルゴリズム L をレーマーの方法として与え、アルゴリズム X で拡張されたユークリッド アルゴリズムを記述します (コードを使用して)。 )元のユークリッド アルゴリズム、最新のユークリッド アルゴリズム、バイナリ アルゴリズム、および拡張ユークリッド アルゴリズムについては、私のブログを参照してください。

この論文では、コードを含むシェーンハーゲのアルゴリズムのいくつかのバージョンについて適切に説明しています。

于 2012-05-21T23:12:45.177 に答える
0

user448810 さん、ご回答ありがとうございます。そのバイナリ アルゴリズムは私にとって完璧であり、非常に高速です。メモリと再帰呼び出しを節約するために、非再帰形式に変換します。これが私の longnum lib の実装で、標準の演算子/関数とは異なる行にいくつかの rem を追加しました

longnum gcd(longnum x,longnum y)
    {
    x.sig=+1; x.integer(); // x=abs(int(x))
    y.sig=+1; y.integer(); // y=abs(int(y))
    longnum z; int x0,y0,sh=0;
    for (;;)
        {
        if (x.iszero()) { z=y; break; } // if (!x) ...
        if (y.iszero()) { z=x; break; } // if (!y) ...
        x0=x.a[_longnum_a1]&1; // x0=x&1
        y0=y.a[_longnum_a1]&1; // y0=y&1
        if ((!x0)&&(!y0)) { x>>=1; y>>=1; sh++; continue; }
        if (!x0) { x>>=1; continue; }
        if (!y0) { y>>=1; continue; }
        if (x<y) y-=x;
        else     x-=y;
        }
    return (z<<sh);
    }
于 2013-08-18T11:04:54.010 に答える