●概要 原理や基本的な方法については理解できた。先ずは、導入に伴う基本的事項の確認や準備から始める。 ●基数の検討 ○検討の必要性 DFTで問題なのは、一貫して整数が維持できるかどうかである。FFT乗算は、整数乗算なのでこれは重要となる。ポイントは演算中、常に整数有効桁を守れるかである。最も、注意すべきは、畳み込みに置ける、総和部分で、最大部分は、 配列数 * (基数 - 1)2 である。この値が、採用したデータ型にて、整数を維持できるかとなる。複素演算は例外なくDouble(倍長浮動小数点)となるので、Doubleに於ける整数有効桁で決まる。また、最終的に、Longにて正確に整数を再現できる条件も必要となる。 実際には、線形化するため、半分が0の数値なので、総和の最大は配列数の半分で良いが、安全係数とする。 ○条件式 Doubleの仮数部は52ビットで、整数有効桁は、余裕を見て15桁となる。つまり、1015 までなら、整数を維持できる(これは、Longでは楽勝の範囲である)。これより、 配列数 * (基数 - 1)2 ＜ 1015 が、条件式となる。これは、基数と配列数(精度)とのトレードオフとなる。精度をだすには、基数を小さくすると言うことになり、演算時間が延びる(乗算回数が増加する)方向となる。 ○基数対精度表 上記の不等式を解くと、以下の表が得られた。1億進数では。もはや破綻している。切れが良く、データ型に一致し、まあまあの精度が得られるのは、基数10,000であろうか。 ちなみに、.NET + DOS/V では、6兆桁が限界のようだ。
2006/4/7 安全最大桁値(線形畳込み)に修正 ●FFT乗算導入のための基数 10,000 とする。10進4桁単位で、Short配列を採用する。理論上、2千万桁が安全な最大となる。今の1億進数との共存を検討する必要がある。 |