FFTを用いて多倍長乗算をしてみた

FFTを用いると多桁の乗算が高速に計算できます。
私はFFTについて良く分からないので、汎用 FFT パッケージで公開されいるものをありがたく使わせて頂くことにしました。(使用したのは fft.zip 内の fftsg.c )

また、FFTを用いた乗算方法についてはFFTとAGMによる円周率計算プログラムというページにと以下のような記述がありました。

1. a，b の各桁を数列 a_j，b_j とおいて，それに対する 離散フーリエ変換 A_k，B_k を FFT で計算する．
   
2. C_k = A_k * B_k を計算して C_k に対して逆 FFT を行って 畳み込み c_j を得る．
   
3. c_j を c_j < 計算の進数 となるように正規化して 乗算 c を得る．
   

このことを踏まえ、このプログラムを書きました。
このプログラムは例として 985617673431 * 712375473872 を計算します。

また、BCC5.5.1でコンパイルするには以下のようにします。
bcc32 fft_mul.c fftsg.c

プログラム中、以下のような記述がありますが、これについては良く分かりませんが、こうしないと計算できません。
c[0]=a[0]*b[0];
c[1]=a[1]*b[1];

追加
上のサンプルプルグラムでは桁数を多くすると正しく計算できないことが判りました。正しく計算出来ように直したのがこのプログラムです。

関連
円周率計算ソフト Windows版
逆数を求めるプログラム
円周率１００万桁を計算する

人気ベスト２０(ページ内)
トップページに戻る
作成日2005/6/8,最終更新日2008/04/11