15.3.3 準2乗GCD

入力値がGCD_DC_THRESHOLDよりも大きい時には，GCDはHGCD (Half GCD)関数を経由して計算します。これはLehmerのアルゴリズムの一般形です。

入力値a,bのサイズをNリムとします。S = floor(N/2) + 1とすると，HGCD(a,b)は変換行列 Tを生成し，この要素は全て非負 になります。さすれば(c;d) = T^{-1} (a;b)にできます。こうして作られた減次された値c,dはSリムよりは大きくなりますが，その差 abs(c-d)はSリムに収まります。この行列要素のサイズも大体N/2リムになります。

このHGCDはLehmerのアルゴリズムを利用していますが，上記の停止条件を使うと，減次された値と対応する変換行列を半分のコストで返してきます。入力値がHGCD_THRESHOLDを超えていると，HGCDが 再帰的に計算され，Möller (see References)が“On Schönhage’s algorithm and subquadratic integer GCD computation” で提唱している下記のような分割統治法が使用されます。

• HGCDを最大有効N/2リムに対して再帰的に呼び出す。入力値全体に変換行列T_1 を適用し，最大サイズ3N/2まで減次。
• 3N/2リムまで減次された値に対して除算と減算を数回行う。ここが大きな商の場合と異なる点です。
• HGCDを再帰的に，減次された数の最大有効N/2リムに対して呼び出す。導出された変換行列T_2をこの減次された数全体に適用し，更にそのサイズを最大 N/2まで縮める。
• T = T_1 T_2を求める。
• 小さい数の除算と減算を実行して要求を満足するまで行い，結果を返す。

この結果，GCDはLehmerのアルゴリズムに似たHGCDを繰り返して実装されていることが分かります。 Lehmerのアルゴリズムは，mpn_hgcd2関数の中で繰り返し大きい方の2リム分を切り捨て， 変換行列を入力値全体に適用し，準2次GCDはその最大有効リムの3番目を切り捨て (この切り捨てるリムの位置はチューニングパラメータで決定しますが，1/2より大きく，1/3ぐらいが適当 のようです）， mpn_hgcdを呼び出し，その結果得られる変換行列を適用します。 入力値がGCD_DC_THRESHOLD以下の長さになれば，Lehmerのアルゴリズムは残り1回だけ実行すれば良いことになります。

HGCDとGCDの両方の漸近的な計算時間はO(M(N)*log(N))になります。ここで M(N)は二つのNリム長の乗算の計算時間です。