15.3.2 Lehmerのアルゴリズム

Euclidのアルゴリズムを改良したLehmerの方法は， 商の列の最初の部分が，入力値の最大有効桁にのみ依存して決まっているという観察に基づいています。 GMPで使っているのはLehmerのアルゴリズムの一種で， 例えばJebeleanによる (see References)“A Double-Digit Lehmer-Euclid Algorithm” が示している通り， 最大有効リムの二つを分割します。 2つの2リムの入力値の商は2×2行列に1リムごとに格納されます。 これはmpn_hgcd2関数で行っています。この結果，行列は mpn_mul_1 や mpn_submul_1で使われる入力値に適用されます。通常は大体1リムごとに入力値を 削減していきます。滅多にないことですが，商が大きい場合は大きい方の2有効リムを試すだけで計算がストップしてしまうことがあるので，この場合は商は通常の除算で求めるようにして下さい。

結果として得られるアルゴリズムは漸近的に O(N^2)となり， Euclidアルゴリズムや2進分割法と同等程度になります。このアルゴリズムの2乗となる計算部分は mpn_mul_1と mpn_submul_1を呼び出して行っています。小さいサイズの場合は，ここよりも 線型量となっている部分の方が比重が高くなります。つまり，大体N回のmpn_hgcd2関数呼び出し が必要となります。この関数は重要な下記の3つの最適化を行っています。

• mpn_hgcd関数（次節を参照）と同じように厳密性を緩めた方法を使います。 つまり，二つの大きな数の，最大有効リム2つ分を呼び出して生成した行列は，この2数の商の列の最初の部分と 完全に一致しなくてもよい，とするものです。最終的な商は時々ずれることがあります。
• 商は常に小さい，という事実を利用します。どのCPUでも除算のアセンブラ命令は遅いので使用しません。（ 分かりずらい条件分岐をたくさん行えば改善できるとは思いますが）。
• 入力値のリムサイズを２から1.5リムにすることで，2リムの計算から単一リムの計算に切り替え，コストを全体的に 半分にします。