Next: , Previous: , Up: Greatest Common Divisor Algorithms   [Index]


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,dSリムよりは大きくなりますが,その差 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” で提唱している下記のような分割統治法が使用されます。

この結果,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リム長の乗算の計算時間です。