Next: Toom 4-Way Multiplication, Previous: Karatsuba Multiplication, Up: Multiplication Algorithms [Index]
Karatsubaによる定式化は分割統治法の最も単純な適用例で，Toom-CookやFFTアルゴリズムはこの系統の発展形にあたります。Toom-CookアルゴリズムについてはKnuth本の4.3.3節に記述があり，定理 A の後に3-way計算の実例も提示されています。ここではGMPで使っている3-way計算について解説します。
引数がそれぞれ3等分割できるものとします（最初の有効桁部分は残りの2つに比べて1, 2リム短くても良い）。
high low +----------+----------+----------+ | x2 | x1 | x0 | +----------+----------+----------+ +----------+----------+----------+ | y2 | y1 | y0 | +----------+----------+----------+
この3つのパートは下記の二つの多項式の係数として扱います。
X(t) = x2*t^2 + x1*t + x0 Y(t) = y2*t^2 + y1*t + y0
bは，x0, x1, y0，y1と同じ長さの2のべき乗になります。つまり，これらのパートの長さがkリムだとすると， b=2^(k*mp_bits_per_limb)となる訳です。ここで，x=X(b)，y=Y(b)とします。
多項式W(t)=X(t)*Y(t)を作り，その係数が次のように表現できるとします。
W(t) = w4*t^4 + w3*t^3 + w2*t^2 + w1*t + w0
この係数w[i]は確定できますので， x*y=X(b)*Y(b)=W(b)より，最終形はw=W(b)となります。 この係数はそれぞれ大体 b^2となるので，最終形W(b)は下記の和となります。
high low
+-------+-------+
| w4 |
+-------+-------+
+--------+-------+
| w3 |
+--------+-------+
+--------+-------+
| w2 |
+--------+-------+
+--------+-------+
| w1 |
+--------+-------+
+-------+-------+
| w0 |
+-------+-------+
係数w[i]は単純な交差積として表現でき，w4=x2*y2, w3=x2*y1+x1*y2, w2=x2*y0+x1*y1+x0*y2・・・となります。必要となるのは， i,j=0,1,2に対して 9つのx[i]*y[j]で，これは単なる筆算乗算アルゴリズムと同じになります。この代わりに，下記のようなアプローチを取ることもできます。
X(t)とY(t)が得られており，5点でこの積，即ちW(t)の値が得られているものとします。 GMPでは下記の点を使用します。
補間点 補間点における値 t=0 x0 * y0(=w0) t=1 (x2+x1+x0) * (y2+y1+y0) t=-1 (x2-x1+x0) * (y2-y1+y0) t=2 (4*x2+2*x1+x0) * (4*y2+2*y1+y0) t=inf x2 * y2(=w4)
t=-1においては，負数となり得るので，絶対値を扱うようにして符号は別にしておきます。 t=inf においては， 実際の値はX(t)*Y(t)/t^4 in the limit as t approaches infinityと評価されるので，単純にx2*y2 は w4となるものと考えます（ t=0においてはx0*y0 はw0 になります)。
W(t)=w4*t^4+…+w0に各点を代入して計算すると，係数w[i]の線型結合が下記のように得られます。
W(0) = w0 W(1) = w4 + w3 + w2 + w1 + w0 W(-1) = w4 - w3 + w2 - w1 + w0 W(2) = 16*w4 + 8*w3 + 4*w2 + 2*w1 + w0 W(inf) = w4
この結果，5つの未知数を持つ5つの方程式が出ますので，単純な線型計算を行って各未知数w[i]を導出します。
それぞれのW(t)の値に対して相互に加減算を行うと，結果として2のべき乗の除算が数回と，3の除算1回行う必要があり，後者についてはmpn_divexact_by3関数で実行できます (see Exact Division)。
W(t)の値を係数に変換するには補間を使います。W(t)は4次多項式なので，5つの補間点を取れば唯一に決まります。補間点は任意に設定できるので，なるべく効率よく連立一次方程式が解けて係数w[i]が導出できるように取りましょう。
2乗についても，乗算と同じように計算することができますが，この場合は
X(t)が一つだけ与えられていればよいので，単純に5点取って，その値W(t)の2乗を計算します。補間多項式は唯一に定まりますので，toom_interpolate_5ptsサブルーチンを使って，2乗と乗算を行います。
Toom-3アルゴリズムは漸近的にO(N^1.465)となります。この指数の値は log(5)/log(3)で，各サイズの1/3を5回再帰的に使用した結果です。 これによって，Karatsuba乗算のO(N^1.585)より改善できます。多項式の値評価や補間を行う手間を考慮しても，あるサイズ以上の乗算ではメリットが出てきます。
Toom-3アルゴリズムとKaratsuba乗算が交差するリムサイズ近くでは一定の幅でほとんど同じコストの部分がでてきます。
MUL_TOOM33_THRESHOLDはその幅の中で適当に取っていますので，何度かチューニングのためのプログラムを実行してみると，多少上下にバラつきが出てきます。計算時間 vs. リムサイズのグラフを描いてみると，その様子が見て取れます。詳細はtune/READMEを参照して下さい。
Toom-3 の閾値がそこそこ小さいリムサイズを示している時には，Karatsuba と Toom-3 の漸近的アルゴリズムオーダーはあまり正確な時間予測を与えてくれません。当然，オーバーヘッドの影響が出てきますし，再帰ループが実行されていますので，その影響もあるからです。 大きなリムサイズであっても，キャッシュアーキテクチャ等のマシン固有の影響によって実際のパフォーマンスは予測していたものとは異なるケースもままあります。
Karatsuba アルゴリズム (see Karatsuba Multiplication)が与える式は，５回の乗算を実行するToom-3と同等のものになっていますが，複雑なので実際のところは良く分かっていません。
Toom-3アルゴリズムに対しては別の見方がZuras (see References)によって提唱されており，これはxとyをベクトルで表現し，それを分割して，多項式評価と補間を行列乗算として表わすものです。 この行列の逆行列を実際に使用するわけではありませんが，その要素は実際の補間ステップに現れるものよりもずっと大きなものになります。このToom 3-wayアルゴリズムを表現する見方は魅力的ですが，このやり方で実装する必要はあまりなく，例えば，６の除算をビット操作で行うなどの工夫が必要になります。