15.1.5 高次のToom’n’half

以上述べてきたToom-Cookアルゴリズム(see Toom 3-Way Multiplication,see Toom 4-Way Multiplication) は，入力値を任意の個数に分割して実行します。一般に，同じ長さの2つの入力値を r個に分割すると，2*r-1個の点でそれぞれ多項式の評価と乗算を行うことになります。 対称性をフルに活用できれば，4点単位でまとめることができ，これによってより高次のToom’n’halfアルゴリズムが実行できるようになります。

Toom’n’halfとは，一つの入力値に対してたくさんの分割を考えるという意味です。 二つの入力値の長さが異なっていても，仮想的に考えることはできます。 偶数rを選ぶと， Toom-r+1/2 アルゴリズムは 2r個の点を必要とするので，4点の組ができます。

この4点の組は0, inf, +1, -1，+-2^i, +-2^-i を含みます。 各点においては，使い回しのできる多項式評価の計算と，各点における補間操作が入ります。更なる工夫としては， 乗算アルゴリズム全体で，積と同じサイズのメモリバッファの利用回数を減らすということもできます。

現在のGMP実装ではToom-6’n’half と Toom-8’n’halfの両方を利用しています。