15.1.4 Toom 4-Way 乗算

Karatsuba乗算アルゴリズムとToom-3アルゴリズムはそれぞれ引数を2ないし3つの係数に分割しました。 Toom-4アルゴリズムでも同様に引数を4つの係数に分割します。Toom-3乗算の記号を使うと，次のような多項式で表現できます。

X(t) = x3*t^3 + x2*t^2 + x1*t + x0
Y(t) = y3*t^3 + y2*t^2 + y1*t + y0

X(t) と Y(t) を7点で評価して乗算を行い，各点でW(t)の値を出します。GMPでは次の点を使用しています。

補間点	補間点における値
t=0	x0 * y0(=w0)
t=1/2	(x3+2*x2+4*x1+8*x0) * (y3+2*y2+4*y1+8*y0)
t=-1/2	(-x3+2*x2-4*x1+8*x0) * (-y3+2*y2-4*y1+8*y0)
t=1	(x3+x2+x1+x0) * (y3+y2+y1+y0)
t=-1	(-x3+x2-x1+x0) * (-y3+y2-y1+y0)
t=2	(8*x3+4*x2+2*x1+x0) * (8*y3+4*y2+2*y1+y0)
t=inf	x3 * y3(=w6)

Toom-4の加算と減算の回数は，Toom-3よりも大幅に増えますが，t=1 や t=-1では.例えば x2+x0のように再利用できるところが出てきます。

Toom-4は漸近的にO(N^1.404)となり，この指数はlog(7)/log(4)，即ち，元のリムサイズの1/4を7回再帰的に繰り返して実行した結果となります。