浮動小数の比較の実装 - やこ〜ん SuperNova2

一つ前のエントリ: http://d.hatena.ne.jp/saiya_moebius/20090111/1231669765 「float と 80bit FPU」
参考: ��ư�� (Boost の close_at_tolerance についてのドキュメント)

浮動小数な値同士を比較することについて、Boost のドキュメントに ��ư�� という興味深いドキュメントがあることを発見したのでメモ。

Boost のドキュメントにある小数の比較について、私なりきに要約

元となっている参考文献が今手元にないので難だが、とりあえず Boost のドキュメントだけから読み取れた内容をまとめてみた。The art of computer programming をまともに読むべきにかも、こりゃ。

判定法

二つの浮動小数 $\small l$ と $\small r$ がある時に、それらが同等( $\small l \simeq r$ )であるかどうかチェックするための信頼性が高いとされている方法の一つに、Kunuth 氏の文献*1に書かれている方法がある。

この方法は、ある許容値 $\small e$ を決めた上で、

強い基準: $l \simeq r \hspace{7} \Leftrightarrow \hspace{7} |l - r| \le e \times |l| \hspace{7} \cap \hspace{7} |l - r| \le e \times |r|$
弱い基準: $l \simeq r \hspace{7} \Leftrightarrow \hspace{7} |l - r| \le e \times |l| \hspace{7} \cup \hspace{7} |l - r| \le e \times |r|$

という基準のどちらかを用いることで、二つの浮動小数の同値性を判定するというものである。

なお、上の式そのままだとオーバーフローやアンダーフローの可能性があるため、Boost の close_at_tolerance では

強い基準: $l \simeq r \hspace{7} \Leftrightarrow \hspace{7} \frac{|l - r|}{|l|} \le e \hspace{7} \cap \hspace{7} \frac{|l - r|}{|r|} \le e$
弱い基準: $l \simeq r \hspace{7} \Leftrightarrow \hspace{7} \frac{|l - r|}{|l|} \le e \hspace{7} \cup \hspace{7} \frac{|l - r|}{|r|} \le e$

という形に式変形して計算しているそうだ*2。

許容値の決定

また、許容値 $\small e$ の設定は、

各種の単純な演算による浮動小数の丸め誤差の発生するであろう回数 $n$
浮動小数の表せる最小の非ゼロ正数*3 $\varepsilon$

を基に、
$e = \frac{n \hspace{3} \times \hspace{3} \varepsilon}{2}$

という式で算出するという方法があるそうだ。

実装してみた

そこで、Source | SVN | Assembla にて C# で実装してみた。

実装の内容は、上に書いてある内容を boost/test/floating_point_comparison.hpp - 1.37.0 を見ながら実装したものである。

IComparer のみならず、float, double の拡張メソッドも実装してあるので、

1f.EqualsTolerant(1f + float.Epsilon, 32);

のようにも使うことが出来る。

なお、この C# 実装では、IComparer にとどめ、IEqualityComparer *4は実装していない。なぜなら、Equals な二つの値の組については常に HashCode も等しくなくてはならない、という制約があるためである。

$x \simeq x + e$ , $x + e \simeq x + 2e$ , $x + 2e \simeq x + 3e$ という風に同値関係を延々と並べて見ると分かるが、誤差を許容する Equals を実装する場合、あらゆる値に対する HashCode を同じ値にしなくてはならなくなってしまい、意味をなさない実装になってしまうのである。

なお、上の記述を見ても分かるとおり、この IComparer は定義的には半順序であって、全順序でない。例えば $x - e \simeq x + e$ であり、全順序であるためには異なる元について同値になってはならない*5。

半順序であっても、MSDN の IComparer のページをざっと見た限り全順序でないとならないとは書いていないので問題がないはずである。また、今回作った誤差を許容する IComparaer 実装は、半順序とはいえ実際には非常に全順序に近い挙動をするので、おそらくほとんどのシチュエーションで問題なく利用できるはずである。ただし、.net framework がデフォルトでサポートしているソートメカニズムなどは全順序の順序関係が与えられることを想定している*6ので、留意する必要はある。今回の IComparer であれば、たとえば許容値未満の値を公差に持つ等差数列といった、やろうとしていることの原理的にどうしようもない代物をソートしようとしない限り問題なく動くはずではあるが・・・。

*1:The art of computer programming vol II

*2:浮動小数がちょうど 0 だった場合などには注意が必要だと思われるが。

*3:CLI で言うところの Double.Epsilon など

*4:Dictionary などでも使える

*5:≦ か ≧ のどちらか片方になる必要がある

*6:参考: I’m Putting On My Top Hat, Tying Up My White Tie, Brushing Out My Tails — In That Order – Fabulous Adventures In Coding