1.3 アルゴリズム

小学校で学ぶ筆算と同じアルゴリズムを用いると、 桁数を $n$ として、計算量は $O(n^2)$ になり、 これで計算をするのは実際的ではない。 FFT を用いると $O(n\log n)$ の計算量で済むので、 $n$ が大きい場合は FFT を用いるのが普通である。 しかし $n$ があまり大きくないときは、FFT の計算量が最小とはならない。

後述する GMP では、$n$ によってアルゴリズムを切り替えている (付属するマニュアル中の ``Algorithms'' を一読することを強く推奨する)。