1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Theory behind floating point comparisons</title> 5<link rel="stylesheet" href="../../../../boostbook.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../../../../index.html" title="Boost.Test"> 8<link rel="up" href="../floating_point.html" title="Floating point comparison"> 9<link rel="prev" href="floating_points_comparison_impl.html" title="Tolerance-based comparisons"> 10<link rel="next" href="../strings.html" title="Strings and C-strings comparison"> 11</head> 12<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 13<table cellpadding="2" width="100%"><tr> 14<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../../boost.png"></td> 15<td align="center"><a href="../../../../../../../../index.html">Home</a></td> 16<td align="center"><a href="../../../../../../../../libs/libraries.htm">Libraries</a></td> 17<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 18<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 19<td align="center"><a href="../../../../../../../../more/index.htm">More</a></td> 20</tr></table> 21<hr> 22<div class="spirit-nav"> 23<a accesskey="p" href="floating_points_comparison_impl.html"><img src="../../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../floating_point.html"><img src="../../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../../index.html"><img src="../../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="../strings.html"><img src="../../../../../../../../doc/src/images/next.png" alt="Next"></a> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h5 class="title"> 27<a name="boost_test.testing_tools.extended_comparison.floating_point.floating_points_comparison_theory"></a><a class="link" href="floating_points_comparison_theory.html" title="Theory behind floating point comparisons">Theory 28 behind floating point comparisons</a> 29</h5></div></div></div> 30<p> 31 The following is the most obvious way to compare two floating-point values 32 <code class="computeroutput"><span class="identifier">u</span></code> and <code class="computeroutput"><span class="identifier">v</span></code> 33 for being close at a given absolute tolerance <code class="computeroutput"><span class="identifier">epsilon</span></code>: 34 </p> 35<a name="equ1"></a><pre class="programlisting"><span class="identifier">abs</span><span class="special">(</span><span class="identifier">u</span> <span class="special">-</span> <span class="identifier">v</span><span class="special">)</span> <span class="special"><=</span> <span class="identifier">epsilon</span><span class="special">;</span> <span class="comment">// (1)</span> 36</pre> 37<p> 38 However, in many circumstances, this is not what we want. The same absolute 39 tolerance value <code class="computeroutput"><span class="number">0.01</span></code> may 40 be too small to meaningfully compare two values of magnitude <code class="computeroutput"><span class="number">10e12</span></code> and at the same time too little to 41 meaningfully compare values of magnitude <code class="computeroutput"><span class="number">10e-12</span></code>. 42 For examples, see <a class="link" href="floating_points_comparison_theory.html#Squassabia">Squassabia</a>. 43 </p> 44<p> 45 We do not want to apply the same absolute tolerance for huge and tiny 46 numbers. Instead, we would like to scale the <code class="computeroutput"><span class="identifier">epsilon</span></code> 47 with <code class="computeroutput"><span class="identifier">u</span></code> and <code class="computeroutput"><span class="identifier">v</span></code>. The <span class="emphasis"><em>Unit Test Framework</em></span> 48 implements floating-point comparison algorithm that is based on the solution 49 presented in <a class="link" href="floating_points_comparison_theory.html#KnuthII">Knuth</a>: 50 </p> 51<a name="equ2"></a><pre class="programlisting"> <span class="identifier">abs</span><span class="special">(</span><span class="identifier">u</span> <span class="special">-</span> <span class="identifier">v</span><span class="special">)</span> <span class="special"><=</span> <span class="identifier">epsilon</span> <span class="special">*</span> <span class="identifier">abs</span><span class="special">(</span><span class="identifier">u</span><span class="special">)</span> 52<span class="special">&&</span> <span class="identifier">abs</span><span class="special">(</span><span class="identifier">u</span> <span class="special">-</span> <span class="identifier">v</span><span class="special">)</span> <span class="special"><=</span> <span class="identifier">epsilon</span> <span class="special">*</span> <span class="identifier">abs</span><span class="special">(</span><span class="identifier">v</span><span class="special">));</span> <span class="comment">// (2)</span> 53</pre> 54<p> 55 defines a <span class="emphasis"><em>very close with tolerance <code class="computeroutput"><span class="identifier">epsilon</span></code></em></span> 56 relationship between <code class="computeroutput"><span class="identifier">u</span></code> 57 and <code class="computeroutput"><span class="identifier">v</span></code>, while 58 </p> 59<a name="equ3"></a><pre class="programlisting"> <span class="identifier">abs</span><span class="special">(</span><span class="identifier">u</span> <span class="special">-</span> <span class="identifier">v</span><span class="special">)</span> <span class="special"><=</span> <span class="identifier">epsilon</span> <span class="special">*</span> <span class="identifier">abs</span><span class="special">(</span><span class="identifier">u</span><span class="special">)</span> 60<span class="special">||</span> <span class="identifier">abs</span><span class="special">(</span><span class="identifier">u</span> <span class="special">-</span> <span class="identifier">v</span><span class="special">)</span> <span class="special"><=</span> <span class="identifier">epsilon</span> <span class="special">*</span> <span class="identifier">abs</span><span class="special">(</span><span class="identifier">v</span><span class="special">);</span> <span class="comment">// (3)</span> 61</pre> 62<p> 63 defines a <span class="emphasis"><em>close enough with tolerance <code class="computeroutput"><span class="identifier">epsilon</span></code></em></span> 64 relationship between <code class="computeroutput"><span class="identifier">u</span></code> 65 and <code class="computeroutput"><span class="identifier">v</span></code>. 66 </p> 67<p> 68 Both relationships are commutative but are not transitive. The relationship 69 defined in <a class="link" href="floating_points_comparison_theory.html#equ2">(2)</a> is stronger that the relationship 70 defined in <a class="link" href="floating_points_comparison_theory.html#equ3">(3)</a> since <a class="link" href="floating_points_comparison_theory.html#equ2">(2)</a> 71 necessarily implies <a class="link" href="floating_points_comparison_theory.html#equ3">(3)</a>. 72 </p> 73<p> 74 The multiplication in the right side of inequalities may cause an unwanted 75 underflow condition. To prevent this, the implementation is using modified 76 version of <a class="link" href="floating_points_comparison_theory.html#equ2">(2)</a> and <a class="link" href="floating_points_comparison_theory.html#equ3">(3)</a>, 77 which scales the checked difference rather than <code class="computeroutput"><span class="identifier">epsilon</span></code>: 78 </p> 79<a name="equ4"></a><pre class="programlisting"> <span class="identifier">abs</span><span class="special">(</span><span class="identifier">u</span> <span class="special">-</span> <span class="identifier">v</span><span class="special">)/</span><span class="identifier">abs</span><span class="special">(</span><span class="identifier">u</span><span class="special">)</span> <span class="special"><=</span> <span class="identifier">epsilon</span> 80<span class="special">&&</span> <span class="identifier">abs</span><span class="special">(</span><span class="identifier">u</span> <span class="special">-</span> <span class="identifier">v</span><span class="special">)/</span><span class="identifier">abs</span><span class="special">(</span><span class="identifier">v</span><span class="special">)</span> <span class="special"><=</span> <span class="identifier">epsilon</span><span class="special">;</span> <span class="comment">// (4)</span> 81</pre> 82<a name="equ5"></a><pre class="programlisting"> <span class="identifier">abs</span><span class="special">(</span><span class="identifier">u</span> <span class="special">-</span> <span class="identifier">v</span><span class="special">)/</span><span class="identifier">abs</span><span class="special">(</span><span class="identifier">u</span><span class="special">)</span> <span class="special"><=</span> <span class="identifier">epsilon</span> 83<span class="special">||</span> <span class="identifier">abs</span><span class="special">(</span><span class="identifier">u</span> <span class="special">-</span> <span class="identifier">v</span><span class="special">)/</span><span class="identifier">abs</span><span class="special">(</span><span class="identifier">v</span><span class="special">)</span> <span class="special"><=</span> <span class="identifier">epsilon</span><span class="special">;</span> <span class="comment">// (5)</span> 84</pre> 85<p> 86 This way all underflow and overflow conditions can be guarded safely. 87 The above however, will not work when <code class="computeroutput"><span class="identifier">v</span></code> 88 or <code class="computeroutput"><span class="identifier">u</span></code> is zero. In such 89 cases the solution is to resort to a different algorithm, e.g. <a class="link" href="floating_points_comparison_theory.html#equ1">(1)</a>. 90 </p> 91<h4> 92<a name="boost_test.testing_tools.extended_comparison.floating_point.floating_points_comparison_theory.h0"></a> 93 <span class="phrase"><a name="boost_test.testing_tools.extended_comparison.floating_point.floating_points_comparison_theory.tolerance_selection_consideratio"></a></span><a class="link" href="floating_points_comparison_theory.html#boost_test.testing_tools.extended_comparison.floating_point.floating_points_comparison_theory.tolerance_selection_consideratio">Tolerance 94 selection considerations</a> 95 </h4> 96<p> 97 In case of absence of domain specific requirements the value of tolerance 98 can be chosen as a sum of the predicted upper limits for "relative 99 rounding errors" of compared values. The "rounding" is 100 the operation by which a real value 'x' is represented in a floating-point 101 format with 'p' binary digits (bits) as the floating-point value <span class="bold"><strong>X</strong></span>. The "relative rounding error" is 102 the difference between the real and the floating point values in relation 103 to real value: <code class="computeroutput"><span class="identifier">abs</span><span class="special">(</span><span class="identifier">x</span><span class="special">-</span><span class="identifier">X</span><span class="special">)/</span><span class="identifier">abs</span><span class="special">(</span><span class="identifier">x</span><span class="special">)</span></code>. 104 The discrepancy between real and floating point value may be caused by 105 several reasons: 106 </p> 107<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 108<li class="listitem"> 109 Type promotion 110 </li> 111<li class="listitem"> 112 Arithmetic operations 113 </li> 114<li class="listitem"> 115 Conversion from a decimal presentation to a binary presentation 116 </li> 117<li class="listitem"> 118 Non-arithmetic operation 119 </li> 120</ul></div> 121<p> 122 The first two operations proved to have a relative rounding error that 123 does not exceed 124 </p> 125<pre class="programlisting"><span class="identifier">half_epsilon</span> <span class="special">=</span> <span class="identifier">half</span> <span class="identifier">of</span> <span class="identifier">the</span> <span class="char">'machine epsilon value'</span> 126</pre> 127<p> 128 for the appropriate floating point type <code class="computeroutput"><span class="identifier">FPT</span></code> 129 <a href="#ftn.boost_test.testing_tools.extended_comparison.floating_point.floating_points_comparison_theory.f0" class="footnote" name="boost_test.testing_tools.extended_comparison.floating_point.floating_points_comparison_theory.f0"><sup class="footnote">[9]</sup></a>. Conversion to binary presentation, sadly, does not have 130 such requirement. So we can't assume that <code class="computeroutput"><span class="keyword">float</span><span class="special">(</span><span class="number">1.1</span><span class="special">)</span></code> 131 is close to the real number <code class="computeroutput"><span class="number">1.1</span></code> 132 with tolerance <code class="computeroutput"><span class="identifier">half_epsilon</span></code> 133 for float (though for 11./10 we can). Non-arithmetic operations either 134 do not have a predicted upper limit relative rounding errors. 135 </p> 136<div class="note"><table border="0" summary="Note"> 137<tr> 138<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../../../../../../doc/src/images/note.png"></td> 139<th align="left">Note</th> 140</tr> 141<tr><td align="left" valign="top"><p> 142 Note that both arithmetic and non-arithmetic operations might also 143 produce others "non-rounding" errors, such as underflow/overflow, 144 division-by-zero or "operation errors". 145 </p></td></tr> 146</table></div> 147<p> 148 All theorems about the upper limit of a rounding error, including that 149 of <code class="computeroutput"><span class="identifier">half_epsilon</span></code>, refer 150 only to the 'rounding' operation, nothing more. This means that the 'operation 151 error', that is, the error incurred by the operation itself, besides 152 rounding, isn't considered. In order for numerical software to be able 153 to actually predict error bounds, the <span class="bold"><strong>IEEE754</strong></span> 154 standard requires arithmetic operations to be 'correctly or exactly rounded'. 155 That is, it is required that the internal computation of a given operation 156 be such that the floating point result is the exact result rounded to 157 the number of working bits. In other words, it is required that the computation 158 used by the operation itself doesn't introduce any additional errors. 159 The <span class="bold"><strong>IEEE754</strong></span> standard does not require 160 same behavior from most non-arithmetic operation. The underflow/overflow 161 and division-by-zero errors may cause rounding errors with unpredictable 162 upper limits. 163 </p> 164<p> 165 At last be aware that <code class="computeroutput"><span class="identifier">half_epsilon</span></code> 166 rules are not transitive. In other words combination of two arithmetic 167 operations may produce rounding error that significantly exceeds <code class="computeroutput"><span class="number">2</span><span class="special">*</span><span class="identifier">half_epsilon</span></code>. 168 All in all there are no generic rules on how to select the tolerance 169 and users need to apply common sense and domain/ problem specific knowledge 170 to decide on tolerance value. 171 </p> 172<p> 173 To simplify things in most usage cases latest version of algorithm below 174 opted to use percentage values for tolerance specification (instead of 175 fractions of related values). In other words now you use it to check 176 that difference between two values does not exceed x percent. 177 </p> 178<p> 179 For more reading about floating-point comparison see references below. 180 </p> 181<h5> 182<a name="boost_test.testing_tools.extended_comparison.floating_point.floating_points_comparison_theory.h1"></a> 183 <span class="phrase"><a name="boost_test.testing_tools.extended_comparison.floating_point.floating_points_comparison_theory.bibliographic_references"></a></span><a class="link" href="floating_points_comparison_theory.html#boost_test.testing_tools.extended_comparison.floating_point.floating_points_comparison_theory.bibliographic_references">Bibliographic 184 references</a> 185 </h5> 186<div class="variablelist"> 187<p class="title"><b>Books</b></p> 188<dl class="variablelist"> 189<dt><span class="term"><a name="KnuthII"></a>The art of computer programming (vol II)</span></dt> 190<dd><p> 191 Donald. E. Knuth, 1998, Addison-Wesley Longman, Inc., ISBN 0-201-89684-2, 192 Addison-Wesley Professional; 3rd edition. (The relevant equations 193 are in §4.2.2, Eq. 36 and 37.) 194 </p></dd> 195<dt><span class="term">Rounding near zero, in <a href="http://www.amazon.com/Advanced-Arithmetic-Digital-Computer-Kulisch/dp/3211838708" target="_top">Advanced 196 Arithmetic for the Digital Computer</a></span></dt> 197<dd><p> 198 Ulrich W. Kulisch, 2002, Springer, Inc., ISBN 0-201-89684-2, Springer; 199 1st edition 200 </p></dd> 201</dl> 202</div> 203<div class="variablelist"> 204<p class="title"><b>Periodicals</b></p> 205<dl class="variablelist"> 206<dt><span class="term"><a name="Squassabia"></a><a href="https://adtmag.com/articles/2000/03/16/comparing-floats-how-to-determine-if-floating-quantities-are-close-enough-once-a-tolerance-has-been.aspx" target="_top">Comparing 207 Floats: How To Determine if Floating Quantities Are Close Enough Once 208 a Tolerance Has Been Reached</a></span></dt> 209<dd><p> 210 Alberto Squassabia, in C++ Report (March 2000) 211 </p></dd> 212<dt><span class="term">The Journeyman's Shop: Trap Handlers, Sticky Bits, and Floating-Point 213 Comparisons</span></dt> 214<dd><p> 215 Pete Becker, in C/C++ Users Journal (December 2000) 216 </p></dd> 217</dl> 218</div> 219<div class="variablelist"> 220<p class="title"><b>Publications</b></p> 221<dl class="variablelist"> 222<dt><span class="term"><a href="http://dl.acm.org/citation.cfm?id=103163" target="_top">What Every 223 Computer Scientist Should Know About Floating-Point Arithmetic</a></span></dt> 224<dd><p> 225 David Goldberg, pages 150-230, in Computing Surveys (March 1991), 226 Association for Computing Machinery, Inc. 227 </p></dd> 228<dt><span class="term"><a href="http://hal.archives-ouvertes.fr/docs/00/07/26/81/PDF/RR-3967.pdf" target="_top">From 229 Rounding Error Estimation to Automatic Correction with Automatic Differentiation</a></span></dt> 230<dd><p> 231 Philippe Langlois, Technical report, INRIA 232 </p></dd> 233<dt><span class="term"><a href="http://www.cs.berkeley.edu/~wkahan/" target="_top">William Kahan 234 home page</a></span></dt> 235<dd><p> 236 Lots of information on floating point arithmetics. 237 </p></dd> 238</dl> 239</div> 240<div class="footnotes"> 241<br><hr style="width:100; text-align:left;margin-left: 0"> 242<div id="ftn.boost_test.testing_tools.extended_comparison.floating_point.floating_points_comparison_theory.f0" class="footnote"><p><a href="#boost_test.testing_tools.extended_comparison.floating_point.floating_points_comparison_theory.f0" class="para"><sup class="para">[9] </sup></a> 243 <span class="bold"><strong>machine epsilon value</strong></span> is represented 244 by <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">numeric_limits</span><span class="special"><</span><span class="identifier">FPT</span><span class="special">>::</span><span class="identifier">epsilon</span><span class="special">()</span></code> 245 </p></div> 246</div> 247</div> 248<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 249<td align="left"></td> 250<td align="right"><div class="copyright-footer">Copyright © 2001-2020 Boost.Test contributors<p> 251 Distributed under the Boost Software License, Version 1.0. (See accompanying 252 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 253 </p> 254</div></td> 255</tr></table> 256<hr> 257<div class="spirit-nav"> 258<a accesskey="p" href="floating_points_comparison_impl.html"><img src="../../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../floating_point.html"><img src="../../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../../index.html"><img src="../../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="../strings.html"><img src="../../../../../../../../doc/src/images/next.png" alt="Next"></a> 259</div> 260</body> 261</html> 262
