Home > IS > FFTによる多倍長乗算

FFTによる多倍長乗算

2006-11-27 (Mon) 5:11
IS

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

Comments:0

Trackbacks:0

Trackback URL for this entry: http://kzk9.net/blog/2006/11/fft.html/trackback
Listed below are links to weblogs that reference: FFTによる多倍長乗算 from moratorium

Home > IS > FFTによる多倍長乗算