2006年11月27日
FFTによる多倍長乗算
FFTを使うと多倍長乗算のオーダーをnlog(n)に落とせて乗算が速くなるよという話だったんだが実装が結構つらかった...。Web上にFFTのプログラムなんてのはごろごろ転がってるけど理論から理解しないと見ても分からないんだよなぁ。
結局、Cooley-Tukey FFT algorithmを再帰を使う分かりやすいプログラムにして実装。ビット反転を使用してバタフライ演算を実現する気力は無かった。これをアセンブラでゴリゴリ書いたら円周率とか高速に求まって嬉しいんだろう。
今から筆算方式の乗算を適当に書いた後レポートを書いて提出予定。徹夜つらい。
追記:
出した。1 << 16桁ぐらいで筆算方式が遅すぎて時間計測できなくなった。
- by
- at 05:11
comments