浮動小数点数の比較アルゴリズム

ホーム
イントロダクション
許容値の選び方
close_at_toleranceアルゴリズム
編集
謝辞
参考

イントロダクション

とても大きな数値は小さな数値では、abs(f1-f2) <= eというシンプルな解放では浮動小数点数の 等値チェックはうまくいかないことがある。そのため、operator=(...)の使用はふさわしくないと言える。 この浮動小数点数比較アルゴリズムはより信頼性の高い、Knuthの[1]の文献で紹介されている方法を元にしている。 不動小数点数 u と v 、許容値 e が与えられたとする。

これらの関係は交換可能であるが、他動的ではない。式(1)で定義された関係 は、式(2)で定義された関係よりも強い(i.e. (1) => (2) )。 式の右辺の積が、不必要なアンダーフローの状態になることがあり、すべてのアンダーフロー、 オーバーフローを安全に回避できるように、実際の実装では、これらの式(1)および(2) ではこれらの改定版が用いられている。

許容値の選び方

領域の詳細な仕様がない場合、許容値は予想される値比較における"相対丸め誤差" の上限値の合計から選択することができる。"丸め"は実数値'x'を'p'二進数(ビット) の浮動小数点数のフォーマットである、浮動小数点数'X'と表現するための操作のことである。 "相対丸め誤差"は実数値における、実数値と浮動小数点数値の差、|x-X|/|x|のことである。 実数値と浮動小数点数値の不一致は以下のような理由で発生する。

• 上位型への変換
• 算術演算
• 10進数表現から2進数表現への変換
• 非算術演算

最初の二つの演算は浮動小数点型の"マシンイプシロン値" (std::numeric_limits<FPT>::epsilon()で表現される)の1/2を超えない相対丸め誤差を 改善することができる。2進数表現に変換する場合、残念ながら、このようなことをしてくれない。 そのため、11./10といった浮動小数点数において、 浮動小数点数の1.1が実数の1.1とくらべて、1/2の"マシンイプシロン値" という許容値内に収まっているかということを想定することはできないのである。 非算術演算もまた、丸め誤差の上限値を予測することはできない。算術演算も、非算術演算も 他の"非丸め"誤差を引き起こす場合がある。アンダーフロー、オーバーフロー、ゼロ除算、 '演算エラー'などである。

1/2イプシロンを含め、すべての丸め誤差の定理は丸め操作 のみを扱っている。 これは、丸め誤差以外の、演算過程によって生じる'演算誤差'が考慮されていないという意味である。 数値演算のためのソフトウェアでは誤差範囲を予想するために、数値演算が'正確、もしくは正しい丸め' を行うことがIEEE754によって要求される。これは、浮動小数点数による内部演算が、 正確にワーキングビット数分に丸めることを要求 されるということである。いいかえれば、演算に用いられる計算が、新たなる誤差を含んではならない ということである。IEEE754標準は非数値演算に対しては同じ結果を求めていない。 アンダーフロー、オーバーフロー、ゼロ除算エラーは丸め誤差の上限値を予期せぬ範囲にまで押し上げて しまう可能性がある。

いくつかの浮動小数点数の定数や演算が含まれるようなシンプルな場合には、以下の式で丸め誤差の数値に 関して、許容値を計算することができる。

数値nは丸め誤差の数である。

浮動小数点数の比較に関してのさらに詳しい情報は最後の参照の所にまとまっている。

close_at_tolerance アルゴリズム

close_at_tolerance アルゴリズムは式(1) および (2)の関係を調べるものである。これは2進数の予想値として実装されている。

template<typename FPT>
class close_at_tolerance
{
public:
    close_at_tolerance( FPT tolerance, bool strong_or_weak = true );
    close_at_tolerance( int number_of_rounding_errors,
                        bool strong_or_weak = true );

    bool operator()( FPT left, FPT right ) const;
};

最初のコンストラクタは比較に用いる許容値を受け取ることができる。 ２番目のコンストラクタは丸め誤差の数を与えることができ、式(3)によって 許容値が計算される。strong_or_weakによって、チェックに用いる関係式を選択できる。デフォルト では、式(1)で定義された強い関係で調べるように設定されている。

編集

close_at_toleranceアルゴリズムは ヘッダファイルfloating_point_comparison.hpp の中に定義されている。 これはtest_tools.hppの中に定義されたテストツールで 使用されることを推奨する。しかし、現状では floating_point_comparison.hppヘッダファイルは自動的にはインクルードされないため、手動でインクルード する必要がある。

謝辞

boostのフォーラムでは、Fernando Cacciolaが非常に役に立つ、浮動小数点数のための 議論につきあってくれた。

参考

[1] Knuth D.E. The art of computer programming (vol II).
[2] David Goldberg What Every Computer Scientist Should Know About Floating-Point Arithmetic
[3] Kulisch U. Rounding near zero.
[4] Philippe Langlois From Rounding Error Estimation to Automatic Correction with Automatic Differentiation
[5] Lots of information on William Kahan home page
[4] Alberto Squassabia Comparing Floats: How To Determine if Floating Quantities Are Close Enough Once a Tolerance Has Been Reached C++ Report March 2000.
[5] Pete Becker The Journeyman's Shop: Trap Handlers, Sticky Bits, and Floating-Point Comparisons C/C++ Users Journal December 2000.