mp.NET.zip (VB.Netバージョン)
基数は256。FFTはNUMERICAL RECIPESのfour1による。
mp4g.NET.zip (VB.Netバージョン)
基数は256。FFTは大浦氏のfft4g_hによる。
mp4g10.NET.zip (VB.Netバージョン)
基数は10進数、デフォルトで10000。FFTは大浦氏のfft4g_hによる。
以下の機能を備えたVB.Netのモジュールです。ここで「桁」とは基数でまとめて数えるものとします。基数が256の場合「1桁」と「1バイト」は同じになります。基数が10000の場合「1桁」は10進数では4桁になります。詳しくはzipファイルに含まれているドキュメントをご覧ください。
-
加減算：m桁同士の符号なし整数の加減算。
-
負数：m桁の符号なし整数に対して、2の補数表現の負数を返す。
-
乗算：m桁とn桁の符号なし整数の乗算。高速フーリエ変換の処理を応用して高速演算。
-
逆数：m桁のデータの逆数をn桁で返す。先頭桁と2番目の桁の間に小数点があるものと仮定。
-
除算：m桁の符号なし整数をn桁の符号なし整数で除し、剰余を求める。逆数と乗算のルーチンの組み合わせによる。
-
短い加算、乗算、除算：m桁と1桁の符号なし整数の演算。
-
平方根：m桁のデータの平方根と平方根の逆数ををn桁で返す。先頭桁と2番目の桁の間に小数点があるものと仮定。
ここまでは、
NUMERICAL RECIPES in C++(英語版)
The Art of Scientific Computing / Second Edition
William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery
CAMBRIDGE UNIVERSITY PRESS
ISBN0-521-75033-4
に記載されたC++によるアルゴリズムを移植、ないし参考にしたものです。mp.NET.zipとmp4g.NET.zipは、基数が256で10進数ではありませんので、計算結果を表示するために基数変換が必要です。このため、以下の機能が加えてあります。mp4g10.NET.zipには、この機能は不要です。
-
整数の文字列変換：mバイトの符号なし整数(256進数でm桁の整数)を10進数で表示した文字列に変換する。mバイトに対して、約2.4×m桁の10進数になる。
-
小数の文字列変換：バイト配列の小数(256進数)を指定した桁数の10進数の文字列に変換する。先頭バイトの前に小数点があるものと仮定。10進数の桁数をdcとすると、元のデータは約dc/2.4バイト必要。
基数と乗算精度について
これらの演算、変換は、Byte型(1バイト整数)あるいはShort型(2バイト整数)を基にしてコーディングしました。しかし、インテルのIA32アーキテクチャを考えれば、さらに長い4バイトの整数型を使えば演算効率は改善するように思われます。しかし、Byte型やShort型でなければならない理由が、乗算のフーリエ変換で用いる浮動小数点Double型(仮数部53ビット)の精度にあります。
整数データひとつを「桁」と考える、つまり、Byte型なら1バイト(基数256)で1桁、2バイト整数型なら2バイト(基数65536)で1桁と考えることにします。N桁×N桁の乗算では、フーリエ変換の過程で、基数の2乗にNを掛けた数値を正確に浮動小数点型の変数に格納できなければなりません。さらに、計算過程の丸め誤差に備えて、多少(4～5bit程度)の余裕が必要です。
このようなことを考慮すると、53bitの精度を持つDouble型を用いてフーリエ変換を行なう場合、Byte型で完全な精度で掛け算が可能なのは、基数10で桁数を数えて(普通の10進数で。以下同じ。)10の10乗桁ぐらいまでになります。ところが2バイト整数型を用いる場合は、掛け算可能な桁数が10の6乗桁程度と、大幅に減ってしまいます。さらに、4バイト整数型の場合は、1桁同士の1回の掛け算の結果(最大64bitになり得る)でさえ、Double型に正確に格納することはできません。
このような理由から、まず、256を基数としてByte型を用いたモジュールを用意しました。パーソナルコンピュータ程度であれば精度は事実上無限です。しかし、速度が遅いことが気になるところです。そこで、10進数を基数としてShort型を用いたモジュールを用意しました。基数を10000とした場合、基数が256の場合より数倍速くなります。代わりに、掛け算は400万桁(基数10000)程度、10進数では1600万桁程度までしか安全ではないと思われます。最近のパーソナルコンピュータの速さとメモリ容量をめいっぱい発揮させるためには、基数を1000とするのが最適かもしれません。
乗算のフーリエ変換について
乗算に用いるフーリエ変換は、mp.NET.zipに採用したNUMERICAL RECIPESの場合、長さ1の自明な変換まで分割しています。つまり「基数4」や「基数8」に最適化した変換は用いていません。その点で低速ですが、大変コンパクトなルーチンにまとまっており、教育的には非常に良いものと思います。
「基数4」で最適化されたルーチンを京都大学の大浦氏が公開されているので、移植したものがmp4g.NET.zipやmp4g10.NET.zipです。乗算が約3倍高速になっています。その代わり高速フーリエ変換のソースコードは相当に長いものになっています。