15.1.7 その他の乗算アルゴリズム

前述したToom-Cookアルゴリズム(see Toom 3-Way Multiplication, see Toom 4-Way Multiplication)は任意の長さに入力値を切り分けますが，これは Knuth section 4.3.3 algorithm C に記述があります。現状の実装ではこのやり方は 使っていません。ここではその理由について書きます。

一般にr+1個に入力値を分割すると，値評価と点ごとの乗算が2*r+1個の点において発生します。 4-way法だとこれが7倍になり，5-wayでは 9倍・・・となります。漸近的には， (r+1)-way アルゴリズムを使うとO(N^(log(2*r+1)/log(r+1)))となります。 点ごとの乗算回数はbig-O計算量に加えられていきますが，値の評価と補間に要する時間は r に比例して増え，実際の計算時間に多大な影響を与えます。各rの漸近的挙動は サイズが大きくなるごとに現実化していきます。オーバーヘッドはO(N*r)となります。 r=2^k FFTにおいては，O(N*log(r))ぐらいになります。

Knuth本のアルゴリズム C では，各点, 0,1,2,…,2*r毎に値の評価を行っていますが， 練習問題 4にあるように -r,…,0,…,rを使うと，後に続く計算は値評価の時点で小さい値を乗じるだけで 済みます(むしろ加算するだけで済む）。従って，補間の計算は半分程度で済むようになります。 このアイディアは，最終結果を偶数番号の係数と奇数番号の係数に分割し，アルゴリズムCのC7とC8で 個別に実行することができるようになる，というものです。 C7ステップにおける割る数はj^2となり，C8における乗じる数は2*t*j-j^2となります。

正の点と負の点を通じて偶数と奇数の部分に分割すると，-1を使う部分は1の平方根として 考えることができるようになります。1の4乗根が分かっていれば，更に分割してスピードアップ できるようになりますが，1以外の整数の平方根は通常利用できません。 虚数単位i=sqrt(-1)を使って複素整数を導入しても役に立ちません。というのも，本質的には 直交座標系では，複素乗算は3つの実数乗算が必要になるからです。 １の2^k'乗根が望ましい環や体の上に存在していれば， Fourier変換は分割して実行でき，O(N*log(r))になります。

浮動小数点FFTは，1のN乗根の近似複素数を使用します。 CPUによっては，このようなFFT用に特別なサポートが備えられていますが，GMPでは，下のビットがずれてしまう可能性が出て正確な乗算を保証できないため，浮動小数点FFTを使っていません。 最後のbit値が1異なっても信号処理にはさしたる影響はありませんが，GMPでは大変な問題になるのです。