libs/test/doc/html/boost_test/testing_tools/extended_comparison/floating_point/floating_points_comparison_theory.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   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">&lt;=</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">&lt;=</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">&amp;&amp;</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">&lt;=</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">&lt;=</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">&lt;=</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">&lt;=</span> <span class="identifier">epsilon</span>
  80 <span class="special">&amp;&amp;</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">&lt;=</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">&lt;=</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">&lt;=</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 &#167;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">&lt;</span><span class="identifier">FPT</span><span class="special">&gt;::</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 &#169; 2001-2019 Boost.Test
 251       contributors<p>
 252         Distributed under the Boost Software License, Version 1.0. (See accompanying
 253         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>)
 254       </p>
 255 </div></td>
 256 </tr></table>
 257 <hr>
 258 <div class="spirit-nav">
 259 <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>
 260 </div>
 261 </body>
 262 </html>