ホーム ] PC技術/システム技術 ] VB.NETプログラミング ] なるほどナレッジ ] インフォメーション ]

上へ
FFT乗算の原理
FFT乗算原理の確認
基数の決定
FFT方式の決定
FFTライブラリ開発
システムへの組込み

FFT乗算

システムへの組込み

最終更新日:2006/11/29 見直し

●概要

 FFT乗算と高速除算ができたが、これを、従来の多倍長クラスに組みことになる。二つの問題を解決する。

●基数問題

 FFTでは基数が10000となっており、従来との整合がとれない。

○解決案1

 従来も、基数を10000にする。つまり、10進4桁単位とする。これは、美しいが、加減算や、一部残るレガシ乗算、除算の速度が、今の半分以下になってしまう。何となく、残念である。

○解決案2

 従来はそのままで、FFT乗算だけ、基数10000とする。このとき、問題となるのは、基数変換の時間である。前後の2回の基数変換が必要となる。これが、FFT乗算時間と比べて、無視できない大きさであると問題となる。15%以下であれば、受け入れられそう。

 幸い、8桁→4桁、4桁→8桁の変換であり、複雑な処理は不要なので(桁数が整数倍で、処理範囲が限定される)、処理時間はそれほどでもないと思われる。以下に、処理時間を実測して見た。

・変換処理(8桁→4桁)

Nは、8桁の場合の配列サイズ
RA()は、8桁の配列
RB()は、4桁の配列

For i = 0 To N - 1
   ii = 2 * i
   U = RA(i) \ Base
   RB(ii + 1) = RA(i) - U * Base     '注意参照
   RB(ii) = U
Next

<注意>

  1. RB(ii + 1) = RA(i) Mod Base とすると、処理時間は筆者のマシンでは、20ns長くなる。-  と * の合せた演算時間の方が、単独の Mod より速いから。CPU演算時間参照。
  2. V = RA(i) と、一旦変数に入れて、二度使うと一見速くなると思うが、RA(i) を2回参照した方が速い。

・変換処理(4桁→8桁)

For i = 0 To N - 1
   ii = i * 2
   RA(i) = RB(ii) * Base + RB(ii + 1)
Next

・測定方法

 上記の処理を1セットとして、データ数を変化させて測定する。

・結果

 対応するFFT乗算時間予測の1% 程度で済むことが分かった。

○結論

 案2を採用する。また、ConvolutionIntegerにオーバーロードを作成し、Integer配列が入力の場合は、Base 8桁 とし、これを、関数にて、直接Double実数として、Base 4桁に変換し、極力、オーバーヘッドを削減する。オブジェクト指向的には、あまり良いオーバーロードではなくなる(モジュールの独立性がなくなる)が、ConvolutionIntegerは、ほぼ乗算にしか利用できないので、ま、良いか。