乗算

多倍長での計算において処理時間、 つまり計算量を決める最も大きな要因は乗算である。 「桁数の大きな数同士の掛け算算」 というと小学校で習った筆算のような手法を考えるが、 この方法では桁数 $n$ に対して $O(n^2)$ の計算量がかかる。 つまり桁数が倍になると計算時間が約 4 倍になるため大きな桁数では効率的ではない。

そのため計算時間を短くするために様々な計算方法が考えられている。 現状では大きな桁数の乗算を行う場合、 FFT やそれに似た計算法を用いた $O(n\log n)$ での計算が最速であるとされている。 [FB03]

実際に計算するプログラムを作成する際には $O$ 表記に現れない、 係数や次数の低い項との関係から桁数に応じて最速となる乗算アルゴリズムは変化する。 また、アルゴリズムによっては計算桁数に制限がある事も含め、 ここでは乗算アルゴリズムのいくつかを紹介する。

アルゴリズムと演算量

筆算方式

名前の通り、小学校で習った筆算のままの演算を行う方法である。 計算量オーダは $O(n^2)$ と大きいが、前後に変換処理が必要ないこと、 作業用メモリを必要としないことなどから桁数が小さい場合には最速となる。

Karatsuba法

$n$ 桁同士の乗算が $O(n^2)$ より効率的にできるやり方を示した 初のアルゴリズム。 $n/2$ 桁ずつに分割し適切に計算していくことで $n/2$ 桁同士の乗算 4 つを 3 つにに分割する。 繰り返し適用させることで計算量は $O(n^{\log_23})$ に下がるが、 乗算が減る代わりに加減算が増えるので適度に分割され計算桁数が小さくなったところで 筆算方式に変更するのが良いだろう。

Toom-Cook法

Toom-Cook 法は Karatsuba 法をさらに発展させた方法で、 多倍長数をいくつかの小多倍長数に分けて効率を上げる。 分割数 $d$ によってプログラム自体を変えることになるので Toom-Cook-3 など数字をつけて呼ばれることもある。 計算量は $O(n^{\log_d(2d-1)})$ となるので $d$ を大きくとればほぼ線形になるように見えるが、 加減算のコストが無視できない程度に大きくなるなどの理由から 現実的には $d=3,4$ 程度までしか使い物にならない。

FFT

FFT は実質的に現在知られる最速アルゴリズムで、計算量は $O(n \log n)$ である。 ここでは包括的に "FFT" としているが、 ここ分類される計算方法には浮動小数点数だけでなく整数剰余環を利用したものや、 それらを再帰的に適用するなど、様々な手法が提唱されている。