15.3.1 2進GCD

短い桁数の場合，GMPはO(N^2)である2進スタイルのGCD アルゴリズムを使用します。これについては Knuth本の4.5.2のアルゴリズムB を初めとして色々なテキストに解説が載っています。このアルゴリズムは， 奇数 a と奇数 bに対しては，次の式を使ってリダクション処理を行っていくというものです。

a,b = abs(a-b),min(a,b)
aから因数2を取り除く

ユークリッド互除法は，Knuth本のアルゴリズム E と Aに解説されているように，商q = floor(a/b) の計算を行い，a,bをv, u - q vに置き換えを繰り返していきます。2進アルゴリズムはこのユークリッド互除法よりも全体的に高速化できます。その理由は，各ステップにおける商が小さい値になり，１，２回の減算を行うだけで，除算を行ったのと同じ効果が得られるからです。 例えば，商が1, 2，3だったとすると，計算時間は67.7%で済みます。詳細はKnuth section 4.5.3 Theorem Eを参照して下さい。

この商が大きい数になると，bはaよりとても小さい値になるので，除算の労力が増大します。これによって，mpn_gcdとmpn_gcd_1 (後者はNx1 と 1x1 の場合にも当てはまる)における，最初の a mod bの労力が減ります。 しかしこの労力の削減によって，大きな商が出現する率が減り，このチェックを行う必要もなくなります。

mpn_gcd_1 関数における最後の1x1 GCDは ，前述の通り，汎用Cコードで実行しています。 2つの値がN-bitであるとすると，このアルゴリズムは1bitあたり0.68回の反復が必要になります。処理を最適化するためには，aから因数2を除去する方法について考える必要があります。

まず最初に，2の補数を取ると，a-bの低い桁のゼロビット数はb-aと同じになりますので， abs(a-b)の計算完了を待たずに，まずa-bに対してゼロビットのカウントを行っていきます。

低い桁のゼロビット除去を行うループは，段々と分岐予測が難しくなっていきます。しかし，平均的には数ビット程度しかないので，１ビット化2ビット除去する程度で済みます（AMD K6ではそうしています）。必要であれば，テーブルを作って数ビットまとめてカウントすることもできます(AMD K7の場合)。他の方法としては，a と bのどちらか一方が奇数になるようにして次のループを回します。

a,b = abs(a-b), min(a,b)
a = a/2 if aが偶数
b = b/2 if bが偶数

これによって，1bitあたり1.25回の反復が必要になりますが，各ステップにおける1bit除去処理における分岐を避けられます。1bit除去を行うことで，大体1bitあたり0.9回反復までコスト削減ができ，トレードオフの価値が出てきます。

このようなアプローチを取ると，一般的には大体1bitあたり6サイクルの速度が出せますが，64bit GCDでは400サイクルぐらいになり，あまり高速になったという感じではありません。GCDに除算可能性のチェックを組み合わせてもあまり効果がない，ということになりますね。

現在の実装では，N < 3の時にのみ，2進GCDアルゴリズムを使うようになっています。