15.2.3 分割統治除算アルゴリズム

割る数がDC_DIV_QR_THRESHOLDより大きいと，除算は分割して実行されます。 正確には，Moenck & Borodin, Jebelean, Burnikel & Ziegler (see References)らによって提唱された 分割統治法を再帰的に呼び出して計算します。

このアルゴリズムは，，2NxN の割算を筆算除法アルゴリズム(see Basecase Division) を実行することで成立しているものです。ベースとして使用するのはN/2リムであって，単一リムでないこと に注意して下さい。こうして，(N/2)x(N/2)の乗算が使用できるようになり， Karatsuba乗算や，他の多倍長乗算のメリットが生かせるようになります(see Multiplication Algorithms). 商の2「桁」分は，Nx(N/2) 除算を繰り返し実行して導出します。

(N/2)x(N/2)乗算は，筆算アルゴリズムを用いて計算されますが， この計算量は筆算除法アルゴリズムと同程度です。但し，関数呼び出し回数が多くなり，乗法とは別に減算の手間が加わります。これらのオーバーヘッドはN/2が MUL_TOOM22_THRESHOLDを超えて，分割統治アルゴリズムを使用するようになると発生します。

DC_DIV_QR_THRESHOLDは割る数のサイズ Nで決まります。MUL_TOOM22_THRESHOLDの2倍を少し 超える程度に設定してありますが，どの程度超えるかはCPU によります。最適化したmpn_mul_basecase 関数は， mpn_submul_1関数を繰り返し呼び出すことで有利にでき，結果として幾分低めのDC_DIV_QR_THRESHOLDになります。

分割統治アルゴリズムは漸近的にO(M(N)*log(N))となります。 ここでM(N)はFFTで実行されるNxN 乗算の計算時間です。 実際の計算時間は， Burnikel & Ziegler論文の2.2節の最後で示されているように，繰り返し用いられるサイズの乗算時間の和になります。例えば，Toom-3アルゴリズムの使用範囲では，分割統治法は 2.63*M(N)になります。 より高次のアルゴリズムを用いると，M(N)の項を改善でき，そこに乗される 値は小さくなり，結果としてlog(N)に近づけることができます。実際には，中～大サイズのものに対しては，2NxN 乗算は2～4倍，NxN乗算よりも遅くなります。