1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
|
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>Floating-point comparison algorithms</title>
<link rel="stylesheet" href="../../../style/style.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.74.0">
<link rel="home" href="../../index.html" title="Boost Test Library">
<link rel="up" href="../testing-tools.html" title="The UTF testing tools or tester's toolbox for all occasions">
<link rel="prev" href="custom-predicate.html" title="Custom predicate support">
<link rel="next" href="reference.html" title="The UTF testing tools reference">
<script language="JavaScript1.2" src="../../../js/boost-test.js"></script>
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table width="100%"><tr>
<td width="10%"><a href="../../index.html"><img alt="Home" width="229" height="61" border="0" src="../../../../../../libs/test/docbook/img/boost.test.logo.png"></a></td>
<td valign="middle" align="left"> > <a href="../../utf.html">The Unit Test Framework</a> > <a href="../testing-tools.html">Testing tools</a><a href="../usage-recommendations.html">
>
</a><b>Floating-point comparison algorithms</b>
</td>
<td><div class="spirit-nav">
<a href="custom-predicate.html"><img src="../../../../../../doc/html/images/prev.png" alt="Prev"></a><a href="reference.html"><img src="../../../../../../doc/html/images/next.png" alt="Next"></a>
</div></td>
</tr></table>
<hr>
<div class="section" lang="en">
<div class="titlepage"><div><div><h4 class="title">
<a name="utf.testing-tools.fpv-comparison"></a>Floating-point comparison algorithms</h4></div></div></div>
<p class="first-line-indented">
In most cases it is unreasonable to use an <code class="computeroutput">operator==(...)</code> for a floating-point values equality check.
The simple, absolute value comparison based, solution for a floating-point values <code class="varname">u</code>,
<code class="varname">v</code> and a tolerance :
</p>
<div class="equation">
<a name="utf.testing-tools.fpv-comparison.eq.1"></a><table class="table">
<colgroup>
<col>
<col>
</colgroup>
<tbody><tr>
<td><div class="informalequation"><span class="mathphrase">
|<code class="varname">u</code> <code class="varname">v</code>|
</span></div></td>
<td class="index">(<span class="bold"><strong>1</strong></span>)</td>
</tr></tbody>
</table>
</div>
<p>
does not produce expected results in many circumstances - specifically for very small or very big values (See
<a class="xref" href="floating_point_comparison.html#bbl.Squassabia" title="Comparing Floats: How To Determine if Floating Quantities Are Close Enough Once a Tolerance Has Been Reached">[<abbr class="abbrev">Squassabia</abbr>]</a> for examples). The <acronym class="acronym">UTF</acronym> implements floating-point comparison algorithm that is
based on the more confident solution first presented in <a class="xref" href="floating_point_comparison.html#bbl.KnuthII" title="The art of computer programming (vol II)">[<abbr class="abbrev">KnuthII</abbr>]</a>:
</p>
<div class="equation">
<a name="utf.testing-tools.fpv-comparison.eq.2"></a><table class="table">
<colgroup>
<col>
<col>
</colgroup>
<tbody><tr>
<td><div class="informalequation"><span class="mathphrase">
|<code class="varname">u</code> <code class="varname">v</code>| |<code class="varname">u</code>| |<code class="varname">u</code> <code class="varname">v</code>| |<code class="varname">v</code>|
</span></div></td>
<td class="index">(<span class="bold"><strong>2</strong></span>)</td>
</tr></tbody>
</table>
</div>
<p>
defines a <em class="firstterm">very close with tolerance </em> relationship between <code class="varname">u</code> and <code class="varname">v</code>
</p>
<div class="equation">
<a name="utf.testing-tools.fpv-comparison.eq.3"></a><table class="table">
<colgroup>
<col>
<col>
</colgroup>
<tbody><tr>
<td><div class="informalequation"><span class="mathphrase">
|<code class="varname">u</code> <code class="varname">v</code>| |<code class="varname">u</code>| |<code class="varname">u</code> <code class="varname">v</code>| |<code class="varname">v</code>|
</span></div></td>
<td class="index">(<span class="bold"><strong>3</strong></span>)</td>
</tr></tbody>
</table>
</div>
<p>
defines a <em class="firstterm">close enough with tolerance </em> relationship between <code class="varname">u</code> and <code class="varname">v</code>
</p>
<p class="first-line-indented">
Both relationships are commutative but are not transitive. The relationship defined by inequations
(<a href="../../" target="_top">2</a>) is stronger
that the relationship defined by inequations (<a href="../../" target="_top">3</a>)
(i.e. (<a href="../../" target="_top">2</a>)
(<a href="../../" target="_top">3</a>)). Because of the multiplication in the right side
of inequations, that can cause an unwanted underflow condition, the implementation is using modified version of the
inequations (<a href="../../" target="_top">2</a>) and
(<a href="../../" target="_top">3</a>) where all underflow, overflow conditions can be
guarded safely:
</p>
<div class="equation">
<a name="utf.testing-tools.fpv-comparison.eq.4"></a><table class="table">
<colgroup>
<col>
<col>
</colgroup>
<tbody><tr>
<td><div class="informalequation"><span class="mathphrase">
|<code class="varname">u</code> <code class="varname">v</code>| |<code class="varname">u</code>| |<code class="varname">u</code> <code class="varname">v</code>| / |<code class="varname">v</code>|
</span></div></td>
<td class="index">(<span class="bold"><strong>4</strong></span>)</td>
</tr></tbody>
</table>
</div>
<div class="equation">
<a name="utf.testing-tools.fpv-comparison.eq.5"></a><table class="table">
<colgroup>
<col>
<col>
</colgroup>
<tbody><tr>
<td><div class="informalequation"><span class="mathphrase">
|<code class="varname">u</code> <code class="varname">v</code>| |<code class="varname">u</code>| |<code class="varname">u</code> <code class="varname">v</code>| / |<code class="varname">v</code>|
</span></div></td>
<td class="index">(<span class="bold"><strong>5</strong></span>)</td>
</tr></tbody>
</table>
</div>
<p class="first-line-indented">
Checks based on equations (<a href="../../" target="_top">4</a>) and
(<a href="../../" target="_top">5</a>) are implemented by two predicates with
alternative interfaces: binary predicate <code class="computeroutput">close_at_tolerance</code><sup>[<a name="id658995" href="#ftn.id658995" class="footnote">8</a>]</sup> and predicate with four arguments
<code class="computeroutput">check_is_close</code><sup>[<a name="id659008" href="#ftn.id659008" class="footnote">9</a>]</sup>.
</p>
<p class="first-line-indented">
While equations (<a href="../../" target="_top">4</a>) and
(<a href="../../" target="_top">5</a>) in general are preferred for the general floating
point comparison check over equation (<a href="../../" target="_top">1</a>), they are
unusable for the test on closeness to zero. The later check is still might be useful in some cases and the <acronym class="acronym">UTF</acronym>
implements an algorithm based on equation (<a href="../../" target="_top">1</a>) in
binary predicate <code class="computeroutput">check_is_small</code><sup>[<a name="id659064" href="#ftn.id659064" class="footnote">10</a>]</sup>.
</p>
<p class="first-line-indented">
On top of the generic, flexible predicates the <acronym class="acronym">UTF</acronym> implements macro based family of tools
<code class="computeroutput"><a class="link" href="reference.html" title="The UTF testing tools reference">BOOST_CHECK_CLOSE</a></code> and <code class="computeroutput"><a class="link" href="reference.html" title="The UTF testing tools reference">BOOST_CHECK_SMALL</a></code>. These tools limit the check
flexibility to strong-only checks, but automate failed check arguments reporting.
</p>
<div class="section" lang="en">
<div class="titlepage"><div><div><h5 class="title">
<a name="utf.testing-tools.fpv-comparison.tolerance-selection"></a>Tolerance selection considerations</h5></div></div></div>
<p class="first-line-indented">
In case of absence of domain specific requirements the value of tolerance can be chosen as a sum of the predicted
upper limits for "relative rounding errors" of compared values. The "rounding" is the operation by which a real
value 'x' is represented in a floating-point format with 'p' binary digits (bits) as the floating-point value 'X'.
The "relative rounding error" is the difference between the real and the floating point values in relation to real
value: |x-X|/|x|. The discrepancy between real and floating point value may be caused by several reasons:
</p>
<div xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class="itemizedlist"><ul type="disc">
<li>Type promotion</li>
<li>Arithmetic operations</li>
<li>Conversion from a decimal presentation to a binary presentation</li>
<li>Non-arithmetic operation</li>
</ul></div>
<p class="first-line-indented">
The first two operations proved to have a relative rounding error that does not exceed
"machine epsilon value" for the appropriate floating point type (represented by
<code class="computeroutput">std::numeric_limits</code><FPT>::epsilon()). Conversion to binary presentation, sadly, does
not have such requirement. So we can't assume that float 1.1 is close to real 1.1 with tolerance
"machine epsilon value" for float (though for 11./10 we can). Non arithmetic operations either do not have a
predicted upper limit relative rounding errors. Note that both arithmetic and non-arithmetic operations might also
produce others "non-rounding" errors, such as underflow/overflow, division-by-zero or 'operation errors'.
</p>
<p class="first-line-indented">
All theorems about the upper limit of a rounding error, including that of epsilon, refer only to
the 'rounding' operation, nothing more. This means that the 'operation error', that is, the error incurred by the
operation itself, besides rounding, isn't considered. In order for numerical software to be able to actually
predict error bounds, the IEEE754 standard requires arithmetic operations to be 'correctly or exactly rounded'.
That is, it is required that the internal computation of a given operation be such that the floating point result
is the exact result rounded to the number of working bits. In other words, it is required that the computation used
by the operation itself doesn't introduce any additional errors. The IEEE754 standard does not require same behavior
from most non-arithmetic operation. The underflow/overflow and division-by-zero errors may cause rounding errors
with unpredictable upper limits.
</p>
<p class="first-line-indented">
At last be aware that epsilon rules are not transitive. In other words combination of two
arithmetic operations may produce rounding error that significantly exceeds 2 epsilon. All
in all there are no generic rules on how to select the tolerance and users need to apply common sense and domain/
problem specific knowledge to decide on tolerance value.
</p>
<p class="first-line-indented">
To simplify things in most usage cases latest version of algorithm below opted to use percentage values for
tolerance specification (instead of fractions of related values). In other words now you use it to check that
difference between two values does not exceed x percent.
</p>
<p class="first-line-indented">
For more reading about floating-point comparison see references below.
</p>
</div>
<div class="bibliography">
<div class="titlepage"><div><div><h3 class="title">
<a name="bbl.fpv-comparison"></a>A floating-point comparison related references</h3></div></div></div>
<div class="bibliodiv">
<h3 class="title">
<a name="bbl.fpv-comparison.books"></a>Books</h3>
<div class="biblioentry">
<a name="bbl.KnuthII"></a><p>[<abbr class="abbrev">KnuthII</abbr>] <span class="title"><i>The art of computer programming (vol II)</i>. </span><span class="author"><span class="firstname">Donald. E.</span> <span class="surname">Knuth</span>. </span><span class="copyright">Copyright 1998 Addison-Wesley Longman, Inc.. </span><span class="isbn">0-201-89684-2. </span><span class="publisher"><span class="publishername">Addison-Wesley Professional; 3 edition. </span></span></p>
</div>
<div class="biblioentry">
<a name="bbl.Kulisch"></a><p>[<abbr class="abbrev">Kulisch</abbr>] <span class="biblioset"><i>Rounding near zero</i>. </span><span class="biblioset"><i><a href="http://www.amazon.com/Advanced-Arithmetic-Digital-Computer-Kulisch/dp/3211838708" target="_top">Advanced Arithmetic for the Digital Computer</a></i>. <span class="author"><span class="firstname">Ulrich W</span> <span class="surname">Kulisch</span>. </span><span class="copyright">Copyright 2002 Springer, Inc.. </span><span class="isbn">0-201-89684-2. </span><span class="publisher"><span class="publishername">Springer; 1 edition. </span></span></span></p>
</div>
</div>
<div class="bibliodiv">
<h3 class="title">
<a name="bbl.fpv-comparison.periodicals"></a>Periodicals</h3>
<div class="biblioentry">
<a name="bbl.Squassabia"></a><p>[<abbr class="abbrev">Squassabia</abbr>] <span class="title"><i><a href="http://www.adtmag.com/joop/carticle.aspx?ID=396" target="_top">Comparing Floats: How To Determine if Floating Quantities Are Close Enough Once a Tolerance Has Been Reached</a></i>. </span><span class="author"><span class="firstname">Alberto</span> <span class="surname">Squassabia</span>. </span><span class="biblioset"><i>C++ Report</i>. <span class="issuenum">March 2000. </span>.
</span></p>
</div>
<div class="biblioentry">
<a name="bbl.Becker"></a><p>[<abbr class="abbrev">Becker</abbr>] <span class="biblioset">“The Journeyman's Shop: Trap Handlers, Sticky Bits, and Floating-Point Comparisons”. <span class="author"><span class="firstname">Pete</span> <span class="surname">Becker</span>. </span></span><span class="biblioset"><i>C/C++ Users Journal</i>. <span class="issuenum">December 2000. </span>.
</span></p>
</div>
</div>
<div class="bibliodiv">
<h3 class="title">
<a name="bbl.fpv-comparison.publications"></a>Publications</h3>
<div class="biblioentry">
<a name="bbl.Goldberg"></a><p>[<abbr class="abbrev">Goldberg</abbr>] <span class="biblioset">“<a href="http://citeseer.ist.psu.edu/goldberg91what.html" target="_top">What Every Computer Scientist Should Know About Floating-Point Arithmetic</a>”. <span class="author"><span class="firstname">David</span> <span class="surname">Goldberg</span>. </span><span class="copyright">Copyright 1991 Association for Computing Machinery, Inc.. </span><span class="pagenums">150-230. </span></span><span class="biblioset"><i>Computing Surveys</i>. <span class="issuenum">March. </span>.
</span></p>
</div>
<div class="biblioentry">
<a name="bbl.Langlois"></a><p>[<abbr class="abbrev">Langlois</abbr>] <span class="title"><i><a href="http://www.inria.fr/rrrt/rr-3967.html" target="_top">From Rounding Error Estimation to Automatic Correction with Automatic Differentiation</a></i>. </span><span class="author"><span class="firstname">Philippe</span> <span class="surname">Langlois</span>. </span><span class="copyright">Copyright 2000. </span><span class="issn">0249-6399. </span></p>
</div>
<div class="biblioentry">
<a name="bbl.Kahan"></a><p>[<abbr class="abbrev">Kahan</abbr>] <span class="title"><i><a href="http://www.cs.berkeley.edu/~wkahan/" target="_top">Lots of information on William Kahan home page</a></i>. </span><span class="author"><span class="firstname">William</span> <span class="surname">Kahan</span>. </span></p>
</div>
</div>
</div>
<div class="footnotes">
<br><hr width="100" align="left">
<div class="footnote"><p><sup>[<a name="ftn.id658995" href="#id658995" class="simpara">8</a>] </sup>check type
and tolerance value are fixed at predicate construction time</p></div>
<div class="footnote"><p><sup>[<a name="ftn.id659008" href="#id659008" class="simpara">9</a>] </sup>check type and tolerance value are the arguments of the
predicate</p></div>
<div class="footnote"><p><sup>[<a name="ftn.id659064" href="#id659064" class="simpara">10</a>] </sup><code class="varname">v</code> is zero</p></div>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright 2001-2007 Gennadiy Rozental</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="custom-predicate.html"><img src="../../../../../../doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../testing-tools.html"><img src="../../../../../../doc/html/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/html/images/home.png" alt="Home"></a><a accesskey="n" href="reference.html"><img src="../../../../../../doc/html/images/next.png" alt="Next"></a>
</div>
</body>
</html>
|
