|
FFT乗算 |
|
システムへの組込み |
| 最終更新日：2007/04/26 見直し |
●概要
FFT乗算と高速除算ができたが、これを、従来の多倍長クラスに組みことになる。二つの問題を解決する。
●基数問題
FFTでは基数が10000となっており、従来との整合がとれない。
○解決案１
従来も、基数を10000にする。つまり、10進4桁単位とする。これは、美しいが、加減算や、一部残るレガシ乗算、除算の速度が、今の半分以下になってしまう。何となく、残念である。
○解決案２
従来はそのままで、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
＜注意＞
- RB(ii + 1) = RA(i) Mod Base とすると、処理時間は筆者のマシンでは、20ns長くなる。- と * の合せた演算時間の方が、単独の Mod より速いから。CPU演算時間参照。
- 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
・測定方法
上記の処理を１セットとして、データ数を変化させて測定する。
・結果
対応するFFT乗算時間予測の1% 程度で済むことが分かった。
○結論
案2を採用する。また、ConvolutionIntegerにオーバーロードを作成し、Integer配列が入力の場合は、Base 8桁 とし、これを、関数にて、直接Double実数として、Base 4桁に変換し、極力、オーバーヘッドを削減する。オブジェクト指向的には、あまり良いオーバーロードではなくなる(モジュールの独立性がなくなる)が、ConvolutionIntegerは、ほぼ乗算にしか利用できないので、ま、良いか。