Alternative Titleチュウシンチ・ハンケイホウシキニヨルセイドホショウツキタバイチョウクカンエンザンライブラリノカイハツ
Note (General)本論文は、精度保証付き数値計算法に基づく多倍長演算ライブラリの研究および実装を含む開発について論ずるものである。計算機で扱える浮動小数点数は有限桁であるため、計算の過程で値を丸める必要がある。このとき発生するのが、丸め誤差である。一回の演算で発生する丸め誤差は小さく、計算結果にはほとんど影響を与えない。しかし、丸め誤差を含む計算結果を引き続く計算に用いると、誤差は伝播・拡大する。このため、最終的な計算結果が非常に大きな誤差を含むことがある。丸め誤差の累積を防ぐ汎用的な手段として、多倍長演算がある。浮動小数点数の仮数部のビット数(桁数) を大きくすれば、発生する丸め誤差は相対的に小さくなり、累積する誤差も小さくなる。どんなに丸め誤差が累積しやすい問題でも、演算の桁数を十分大きくすれば、理論上、誤差を小さく抑えることができる。このように多倍長演算は、丸め誤差の累積を抑えるのに有効な手段であるが、それだけでは、計算結果がどれだけ改善したのかは分からない。その効果を検証するには、何らかの検算が必要である。また、桁数の大きな多倍長演算には多くの記憶領域が必要であり、計算時間もかかる。そこで、求めたい計算結果の精度に対して、演算の桁数を最小限に抑えることが望ましい。例えば、10 進数100 桁程度で計算すれば十分な問題を、10 進数1000 桁で計算するのは、計算機資源の無駄である。このような無駄を削減するには、累積した丸め誤差の大きさを知る必要がある。浮動小数点数演算の丸め誤差を見積る手法として、精度保証付き数値計算がある。精度保証付き数値計算は、一般に機械区間演算によって実装される。区間演算とは、通常の数値の代わりに幅を持った区間同士の演算を行い、計算結果も区間で表す算法である。機械区間演算とは、計算機上の浮動小数点数を用いて実装された区間演算のことである。機械区間演算では、CPU に組み込まれた丸めの方向制御命令などを用いて、発生しうる丸め誤差を包含する区間を計算結果とする。この精度保証付き数値計算を、多倍長演算と組み合わせ、丸め誤差の大きさを把握することが考えられる。機械区間演算の実装では、区間の下端と上端を保持する方法が一般的である。下端・上端方式の機械区間演算の基本は、丸めの方向を変えて同じ計算を二回繰り返すことである。これによって、点(半径を持たない通常の数) の演算の二倍の計算量で精度保証が行える。別の区間表現として、区間の中心値と半径を保持する方法がある。機械区間演算を多倍長に拡張した場合、実装方法を工夫することによって、中心値・半径方式の方が計算速度・メモリ効率の両面で有利になると考えられる。ここでの工夫とは、区間の中心値を多倍長で、半径を低精度で保持することである。半径の表現を低精度で済ませることによって、計算量を点の演算の二倍未満に抑えることができる。半径が低精度であることに起因する誤差もあるが、多倍長区間演算の場合、その影響はほとんど問題にならない。このような実装方法を用いれば、中心値・半径方式の精度保証付き多倍長区間演算は、原理的には下端・上端方式より速くなるはずである。しかし、下端・上端方式より実装が複雑になるというデメリットもあり、理論上の優位性が実現できるかどうかは、不確定であった。精度保証付き計算法の既存ライブラリであるINTLAB は、このアイデアに基づいて実装された精度保証付き多倍長区間演算の機能を持つ。しかし、INTLAB の多倍長区間演算機能は、ライブラリ内部で使用するために作られた簡易的なものであり、そのままでは実用的とは言えず、中心値・半径方式の優位性の検証に用いることはできない。本論文では、INTLAB のアイデアを発展させた新しい精度保証付き多倍長演算ライブラリLILIB の開発を行い、これを実行することで、中心値・半径方式の優位性を検証している。LILIB には、データ構造の無駄の解消、乗算・除算のより誤差が小さいアルゴリズムの実装、平方根の精度保証の実装、厳密な区間の大小比較の実装などの、INTLAB にはない特徴がある。LILIB を用いた数値実験による検証の結果として以下のものを得ている。中心値の桁数が小さいときは、通常の点の演算の二倍以上の時間がかかる区間演算結果もあったが、中心値の桁数が大きければ、四則演算と平方根の計算について、点の演算の二倍未満の計算時間を達成できた。特に加減乗算に限れば、点の演算に数既存の精度保証付き多倍長区間演算ライブラリとの比較では、現時点のLILIB の計算速度は、下端・上端方式を採用するMPFI よりも劣っている。これは、区間演算の土台になっている、点の演算速度の差によるものである。MPFI の点の演算の土台になっているGNU Multi-Precision Library(GMP) は、高速な多倍長演算アルゴリズムの選択と、アセンブラによる各種計算機への最適化により、非常に高速である。GMP の開発はチームプロジェクトであるので、現在の我々の研究態勢では、GMPの速度に追いつく多倍長演算プログラムを独自に開発することは困難であった。しかし、本論文の成果によって、精度保証付き多倍長区間演算に中心値・半径方式を用いることで下端・上端方式より高速化できることは確認できている。そこで、LILIB のアルゴリズムを生かしつつ、点の演算部分をGMP に置き換えれば、既存のものより高速な精度保証付き多倍長演算が実現できるはずである。これについては引き続き開発を進めて行きたい。今後の課題としては、上記の他、各種数学関数の整備・連立一次方程式への対応・微分方程式への対応などが挙げられる。
2015
Collection (particular)国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文
Date Accepted (W3CDTF)2016-07-07T04:28:02+09:00
Data Provider (Database)国立国会図書館 : 国立国会図書館デジタルコレクション