円周率.jp (http://xn--w6q13e505b.jp/method/mult.html)

乗算

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

そのため,計算時間を短くするために様々な計算方法が考えられている. 現状では FFT やそれに似た計算法を用いた O(n log n loglog n) での計算が最速であるとされている.[FB03]

実際に計算するプログラムを作成する際には O 表記に現れない,係数や次数の低い項との関係から桁数 n に応じて最速となる乗算アルゴリズムは変化する. そのため,ここでは乗算アルゴリズムのいくつかを紹介する.

アルゴリズムと演算量

筆算方式

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

Karatsuba法

乗算する数値をそれぞれ 2 分割し, 加減算の回数を増やすことで(分割後の数同士の)乗算回数を 4 回から 3 回へ減らす. 繰り返し適用させることで計算量は $O(n^{\log_23})$ と下がる. また,変換に使う加減算コストの方が大きくなる, $n$ が小さな範囲では筆算方式より効率は悪く, 逆に大きな範囲では Toom-Cook 法や FFT を用いた方法が速くなるため, 実際に適用する範囲は実装と実験により決める必要がある.

Toom-Cook法

Karatsuba 法をさらに発展させた方法. 多倍長数をいくつかの小多倍長数に分けて効率を上げる. 分割数 $d$ に対して計算量が $O(n^{\log_d(2d-1)})$ となり,一見 $d$ を大きくとればほぼ線形になるように見えるが, その場合加減算のコストが大きくなるなどの理由から実際は遅い. 現実的には $d=3,4$ 程度が現実的だが 最速になる $d$ は実験的に定めるしかない. なお $d=2$ の場合は Karatsuba 法と同じアルゴリズムになる.

FFT

現在知られる最速アルゴリズム.計算オーダーは $O(n \log n\log\log n)$ となるが,実際は FFT の中をどうするのか, 剰余環を使った計算を利用するかなどで若干変わる. また,包括的に FFT に分類される中には浮動小数だけでなく整数剰余環を利用したものや, それらを再帰的に適用するなど,様々な計算法が提唱されている. 32 bit マシンばかりだった頃は 64bit 分の乗算が 1 命令でできない, メモリ容量から 1 億桁同士程度の乗算が限界であった, 浮動小数演算では FMA を利用して高い演算効率を実現できた, などの理由から倍精度浮動小数を用いた複素 FFT が最速であったが, 64 bit マシンの普及や整数環 FFT の提唱から,現在, 大きな $n$ に対して具体的なアルゴリズムとしてはどれが最速なのか, という問題に対する解は実質的に出されていない.