|
演算時間予測システム |
|
時間表の生成 |
| 最終更新日：2007/04/26 新規 |
●概要
実測値を元に幾つかの時間表が生成される。
●内容/方法
以下の時間表がある。()内は実際のファイル名
- 四則演算表(msBCTable.csv)
Comp、Add/Subt、MulI、DivI、MulS を、64〜100万桁まで実際に演算し、時間を計測する。MulI、DivIは、多倍長とBaseとの通常演算、MulSとは、多倍長と、短い多倍長との通常乗算。いずれもFFT系演算より高速となる。
- 通常乗除算表(msLMDTable.csv)
通常の方法で乗除算を行い、時間を計測する。但し、この演算は時間が掛かるので、途中で打ち切り、残りは多項式近似で外挿して、テーブルを生成している。
- 短倍長乗算表(msUSTable.csv)
短倍長とは、多倍長であるが、せいぜい千桁程度のもの。多倍長と短倍長の乗算は、FFT乗算より速くなることが多い。
- FFT演算表(msBFTable.csv)
FFT乗算と、逆数除算を100万桁まで演算し、その時間を計測する。
●演算時間表解説
○四則演算表
Comp、Add/Subt、MulI、DivI の通常演算群。 原理的に桁数に比例するので、線形補間にて任意の桁数での時間を求められる。
四則演算表のグラフ
○通常乗除算表
LMul、LDiv の時間。この時間は精度が大きくなると、CPUによっては、数時間になるので、3万桁程度で実測は終了させ、最小自乗法により二次式で近似し、残りを外挿してテーブルを完成させている。但し、値の範囲が大きく、小さな部分では誤差が大きくなるので、1024桁までは実測値、それ以降を二次式で求めている。
通常乗除算のグラフ(外挿結果)(赤がLDiv)
○短倍長乗算表
LMul によるMulS で、S(短い多倍長) として、16、32、64、128、256、512、1024 桁としたもの。 この場合は、二次元テーブルとなる(長いほうの桁と短い方の桁)が、両方向に線形なので、線形補間で求められる。
短倍長乗算表のグラフ
○FFT演算表
FMul、RDiv の時間。FFT系の演算時間は非線形(階段波形)になるので、原理を踏まえて実測する。つまり桁数が、2N と 2N + 1 の間で不連続となるので、実測する場合は、桁数の分解能が 8 桁なので、2N と 2N + 8 のペアで実測する。また、FMulでは 2N + 8 と、2N+1 は、ほぼ原理的に同じ時間となるので、そのように調整する。これにて、階段波形であっても、線形補間が成立する。RDiv では、FMul と少し様子が異なる。2N と 2N + 8 での不連続は同じであるが、2N + 8 と、2N+1 間は、ほぼ線形に変化する。これは、求める桁数とニュートン収束回数がほぼ比例するからである。
FFT演算のグラフ(赤がRDiv)
FMul時間だけのグラフ
○自動選択乗除算
Mul、Div の演算時間。これらに対する表はなく、既存の表と、システム変数にてその都度算出される。