ホーム ] 多倍長語 MegaLong ] 基数変換 ] 数値変換 ] 定数システム ] 演算時間予測システム ]

上へ
収束予測
階乗予測
級数予測
時間予測
限界値自動決定

演算時間予測システム

時間表の生成

最終更新日: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 の演算時間。これらに対する表はなく、既存の表と、システム変数にてその都度算出される。