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

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

FFT乗算

基数の決定

最終更新日:2006/04/18 修正

●概要

 原理や基本的な方法については理解できた。先ずは、導入に伴う基本的事項の確認や準備から始める。

●基数の再検討

○レガシ版

 レガシ版では基数は100,000,000(1億)となっている。これは、Integerで表現でき、単位乗算でオーバーフローが起きなく、10進で8桁単位で分かり良いと言うことで選んでいる。

○再検討の理由

 DFTで問題なのは、一貫して整数が維持できるかどうかである。FFT乗算は、整数乗算なのでこれは重要となる。ポイントは演算中、常に整数有効桁を守れるかである。最も、注意すべきは、畳み込みに置ける、総和部分で、最大部分は、

 配列数 * (基数 - 1)2 

である。この値が、採用したデータ型にて、整数を維持できるかとなる。複素演算は例外なくDouble(倍長浮動小数点)となるので、Doubleに於ける整数有効桁で決まる。また、最終的に、Longにて正確に整数を再現できる条件も必要となる。

 実際には、線形化するため、半分が0の数値なので、総和の最大は配列数の半分で良いが、安全係数とする。

○条件式

 Doubleの仮数部は52ビットで、整数有効桁は、余裕を見て15桁となる。つまり、1015 までなら、整数を維持できる(これは、Longでは楽勝の範囲である)。これより、

 配列数 * (基数 - 1)2  < 1015

が、条件式となる。これは、基数と配列数(精度)とのトレードオフとなる。精度をだすには、基数を小さくすると言うことになり、演算時間が延びる(乗算回数が増加する)方向となる。これは、自然界の根本原理にあっている(良いこと * 悪いこと = C)。

○基数対精度表

 上記の不等式を解くと、以下の表が得られた。一億進数では。もはや破綻している。切れが良く、データ型に一致し、まあまあの精度が得られるのは、基数10,000であろうか。 ちなみに、.NET + DOS/V では、6兆桁が限界のようだ。

基数 単位桁数 配列数 精度(安全最大桁数)
10 1 12,345,679,012,345 6,172,839,506,173
100 2 102,030,405,060 102,030,405,060
1,000 3 1,002,003,004 1,503,004,506
10,000 4 10,002,000 20,004,000
100,000 5 100,002 250,005
1,000,000 6 1,000 3,000
10,000,000 7 10 35
100,000,000 8 0 0

2006/4/7 安全最大桁値(線形畳込み)に修正

 

●FFT乗算導入のための基数

 10,000 とする。10進4桁単位で、Short配列を採用する。理論上、2千万桁が安全な最大となる.