ceph/src/boost/libs/test/doc/testing_tools/testing_floating_points.qbk

   1 [/
   2  / Copyright (c) 2003-2015 Boost.Test contributors
   3  /
   4  / Distributed under the Boost Software License, Version 1.0. (See accompanying
   5  / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6  /]
   7
   8
   9 [/ ################################################ ]
  10 [section:floating_point Floating point comparison]
  11
  12 Unless you specify otherwise, when two values of floating-point type are compared inside assertion  __BOOST_TEST__,
  13 operators `==` and `!=` defined for these types are used. In most cases, however, what we need is not an ['exact] equality (or inequality),
  14 but to check that the two numbers are 'sufficiently close' or 'sufficiently different'. In order to do that we need to provide a ['tolerance]
  15 parameter that will instruct the framework what we consider 'sufficiently close'.
  16
  17 We can define a per-[link ref_test_unit test unit] tolerance for a given floating point type by using
  18 [link boost_test.tests_organization.decorators decorator] __decorator_tolerance__:
  19
  20 [bt_example tolerance_01..specifying tolerance per test case..run-fail]
  21
  22 How the tolerance parameter is processed in detail is described [link boost_test.testing_tools.extended_comparison.floating_point.floating_points_comparison_impl here].
  23
  24 It is possible to specify floating point comparison tolerance per single assertion, by providing ['manipulator] [funcref boost::test_tools::tolerance]
  25 as the second argument to __BOOST_TEST__.
  26
  27 [bt_example tolerance_02..specifying tolerance per assertion..run-fail]
  28
  29 [caution The support for manipulators requires that your compiler supports variadic macros, `auto` for type deduction
  30  and `decltype`. These are C++11 features, but are also available on some pre-C++11 compilers. On compilers that are
  31  lacking these features resort to defining tolerance per test unit, or to compatibility test assertions: __BOOST_CHECK_CLOSE__ and __BOOST_CHECK_SMALL__.]
  32
  33 It is possible to specify the tolerance as percentage. At test unit level, the decorator syntax is:
  34
  35 ```
  36 * boost::unit_test::tolerance( boost::test_tools::fpc::percent_tolerance(2.0) )
  37 // equivalent to: boost::unit_test::tolerance( 2.0 / 100 )
  38 ```
  39
  40 At assertion level, the manipulator syntax is:
  41
  42 ```
  43 2.0% boost::test_tools::tolerance()
  44 boost::test_tools::tolerance( boost::test_tools::fpc::percent_tolerance(2.0) )
  45 // both equivalent to: boost::test_tools::tolerance( 2.0 / 100 )
  46 ```
  47
  48 Manipulator `tolerance` specifies the tolerance only for a single floating-point type. This type is deduced from form
  49 the numeric value passed along the manipulator:
  50
  51 [table
  52 [[expression][semantics]]
  53 [[`tolerance(0.5)`][tolerance for type `double` changed to 0.5]]
  54 [[`tolerance(float(0.5))`][tolerance for type `float` changed to 0.5]]
  55 [[`tolerance(0.5f)`][tolerance for type `float` changed to 0.5]]
  56 [[`tolerance(0.5L)`][tolerance for type `long double` changed to 0.5]]
  57 [[`tolerance(Decimal("0.5"))`][tolerance for a user-defined type `Decimal` changed to the supplied value]]
  58 [[`5.0% tolerance()`][tolerance for type `double` changed to 0.05 (`5.0 / 100`)]]
  59 [[`5.0f% tolerance()`][tolerance for type `float` changed to 0.05]]
  60 [[`Decimal("5.0")% tolerance()`][tolerance for type `Decimal` changed to value `(Decimal("5.0") / 100)`]]
  61 ]
  62
  63 This is also the case for decorator `tolerance`. In case of the decorator, however, it is possible to apply multiple
  64 decorators `tolerance` defining the tolerance for different types.
  65
  66 When values of two different floating point types `T` and `U` are compared, __BOOST_TEST__ uses the tolerance
  67 specified for type `boost::common_type<T, U>::type`. For instance, when setting a tolerance for mixed `float`-to-`double` comparison,
  68 the tolerance for type `double` needs to be set.
  69
  70 Given two floating point types `T` and `U` and their common type `C`, the tolerance specified for type `C` is applied only when
  71 types `T` and `U` are appear as sub-expressions of the full expression inside assertion __BOOST_TEST__. It is not applied when
  72 `T` and `U` are compared inside a function invoked during the evaluation of the expression:
  73
  74 ```
  75 BOOST_AUTO_TEST_CASE(test, * utf::tolerance(0.02))
  76 {
  77   double                  d1 = 1.00, d2 = 0.99;
  78   boost::optional<double> o1 = 1.00, o2 = 0.99;
  79
  80   BOOST_TEST(d1 == d2);   // with tolerance    (double vs. double)
  81   BOOST_TEST(o1 == o2);   // without tolerance (optional vs. optional)
  82   BOOST_TEST(o1 == d2);   // without tolerance (optional vs. double)
  83   BOOST_TEST(*o1 == *o2); // with tolerance    (double vs. double)
  84 }
  85 ```
  86
  87 Finally, note that comparisons for tolerance are also applied to `operator<` with semantics 'less by more than some tolerance`,
  88 and other relational operators. Also, the tolerance-based comparisons are involved when a more complicated expression tree is
  89 processed within the assertion body:
  90
  91 [bt_example tolerance_03..tolerance applied in more complex expressions..run-fail]
  92
  93
  94 [/############################################################################]
  95
  96 [section:customizing_for_tolerance Enabling tolerance for user-defined types]
  97
  98 The __UTF__ recognizes that a given type `T` is suitable for tolerance-based comparisons using the expression
  99 [classref boost::math::fpc::tolerance_based]`<T>::value`. This meta-function already returns true for built-in
 100 floating-point types as well as any other types that match the following compile-time expression:
 101
 102 ```
 103 boost::is_floating_point<T>::value ||
 104     ( std::numeric_limits<T>::is_specialized &&
 105      !std::numeric_limits<T>::is_integer &&
 106      !std::numeric_limits<T>::is_exact)
 107 ```
 108
 109 If you require your type to also participate in tolerance-based comparisons, regardless of the above expression,
 110 you can just specialize [classref boost::math::fpc::tolerance_based] for your type directly, and derive it from
 111 `boost::true_type`. Your type does not even have to be a floating-point type provided that it models concept
 112 [link boost_test.testing_tools.extended_comparison.floating_point.customizing_for_tolerance.concept_tolerance_based `ToleranceCompatible`].
 113
 114 [bt_example tolerance_04..adapting user-defined types for tolerance-based comparison..run-fail]
 115
 116 [h3:concept_tolerance_based Concept `ToleranceCompatible`]
 117
 118 [h4 Refinement of]
 119
 120 `MoveConstructible`, [@http://www.sgi.com/tech/stl/EqualityComparable.html `EqualityComparable`],
 121 [@http://www.sgi.com/tech/stl/LessThanComparable.html `LessThanComparable`]
 122
 123 [h4 Notation]
 124
 125 [table
 126   [[][]]
 127   [[`T`][A type that is a model of `ToleranceCompatible`]]
 128   [[`x`, `y`][objects of type `T`]]
 129   [[`i`, `j`][objects of type `int`]]
 130 ]
 131
 132 [h4 Valid expressions]
 133
 134 [table
 135   [[Name][Expression][Return type]]
 136   [[Conversion from `int`][`T j = i;`][]]
 137   [[Addition][`x + y`][`T`]]
 138   [[Subtraction][`x - y`][`T`]]
 139   [[Negation][`-x`][`T`]]
 140   [[Multiplication][`x * y`[br]`x * i`][`T`]]
 141   [[Division][`x / y`[br]`x / i`][`T`]]
 142   [[Mixed equality][`x == i`[br]`x != i`][`bool`]]
 143   [[Mixed ordering][`x < i`[br]`x > i`[br]`x <= i`[br]`x >= i`][`bool`]]
 144 ]
 145
 146 [h4 Invariants]
 147
 148 [table
 149   [[`T` and `int` consistency][`(x == T(i)) == (x == i)`[br]`(x != T(i)) == (x != i)`[br]`(x < T(i)) == (x < i)`[br]`(x > T(i)) == (x > i)`[br]`(x / T(i)) == (x / i)`[br]`(x * T(i)) == (x * i)`]]
 150 ]
 151
 152 [endsect] [/ customizing_for_tolerance]
 153
 154
 155 [/############################################################################################]
 156
 157 [section:floating_points_comparison_impl Tolerance-based comparisons]
 158
 159
 160 Assertions in the __UTF__ use two kinds of comparison. For `u` being close to zero with absolute tolerance `eps`:
 161
 162 ``
 163    abs(u) <= eps; // (abs)
 164 ``
 165
 166 For `u` and `v` being close with relative tolerance `eps`:
 167
 168 ```
 169    abs(u - v)/abs(u) <= eps
 170 && abs(u - v)/abs(v) <= eps; // (rel)
 171 ```
 172
 173 For rationale for choosing these formulae, see section __floating_points_testing_tools__.
 174
 175
 176 Assertion __BOOST_TEST__ (when comparing floating-point numbers) uses the following algorithm:
 177
 178 * When either value `u` or `v` is zero, evaluates formula (abs) on the other value.
 179 * When the specified tolerance is zero, performs direct (native) comparison between `u` and `v`.
 180 * Otherwise, performs formula (rel) on `u` and `v`.
 181
 182 [note Therefore in order to check if a number is close to zero with tolerance, you need to type:
 183 ```
 184 BOOST_TEST(v == T(0), tt::tolerance(eps));
 185 ```]
 186
 187 The compatibility assertions __BOOST_LEVEL_CLOSE__ and __BOOST_LEVEL_CLOSE_FRACTION__ perform formula (rel).
 188
 189 The compatibility assertion __BOOST_LEVEL_SMALL__ performs formula (abs).
 190
 191 The __UTF__ also provides unary predicate [classref boost::math::fpc::small_with_tolerance `small_with_tolerance`] and binary predicate predicate
 192 [classref boost::math::fpc::close_at_tolerance `close_at_tolerance`] that implement formula (abs) and (rel) respectively.
 193
 194 [h3 Tolerance in `operator<`]
 195
 196 Tolerance-based computations also apply to `operator<` and other relational operators. The semantics are defined as follows:
 197
 198 * ['less-at-tolerance] <==> ['strictly-less] and not ['close-at-tolerance]
 199 * ['greater-at-tolerance] <==> ['strictly-greater] and not ['close-at-tolerance]
 200 * ['less-or-equal-at-tolerance] <==> ['strictly-less] or ['close-at-tolerance]
 201 * ['greater-or-equal-at-tolerance] <==> ['strictly-greater] or ['close-at-tolerance]
 202
 203 [note This implies that the exactly one of these: `u < v`, `u == v`, `u > v`, passes with __BOOST_TEST__ at any given tolerance.]
 204 [caution Relation less-at-tolerance is not a Strict Weak Ordering; using it as predicate in `std::map` or any order-based STL
 205   algorithm would result in undefined behavior.]
 206
 207 [endsect] [/ floating_points_comparison_impl]
 208
 209 [/############################################################################################]
 210
 211 [section:floating_points_comparison_theory Theory behind floating point comparisons]
 212
 213
 214 The following is the most obvious way to compare two floating-point values `u` and `v` for being close at a given absolute tolerance `epsilon`:
 215
 216 [#equ1]
 217 ``
 218    abs(u - v) <= epsilon; // (1)
 219 ``
 220
 221 However, in many circumstances, this is not what we want. The same absolute tolerance value `0.01` may be too small to meaningfully compare
 222 two values of magnitude `10e12` and at the same time too little to meaningfully compare values of magnitude `10e-12`. For examples, see [link Squassabia].
 223
 224 We do not want to apply the same absolute tolerance for huge and tiny numbers. Instead, we would like to scale the `epsilon` with `u` and `v`.
 225 The __UTF__ implements floating-point comparison algorithm that is based on the solution presented in [link KnuthII Knuth]:
 226
 227 [#equ2]
 228 ``
 229    abs(u - v) <= epsilon * abs(u)
 230 && abs(u - v) <= epsilon * abs(v)); // (2)
 231 ``
 232
 233 defines a ['very close with tolerance `epsilon`] relationship between `u` and `v`, while
 234
 235 [#equ3]
 236 ``
 237    abs(u - v) <= epsilon * abs(u)
 238 || abs(u - v) <= epsilon * abs(v); // (3)
 239 ``
 240
 241 defines a ['close enough with tolerance `epsilon`] relationship between `u` and `v`.
 242
 243 Both relationships are commutative but are not transitive. The relationship defined in
 244 [link equ2 (2)] is stronger that the relationship defined in [link equ3 (3)] since [link equ2 (2)] necessarily implies [link equ3 (3)].
 245
 246 The multiplication in the right side of inequations may cause an unwanted underflow condition. To prevent this,
 247 the implementation is using modified version of [link equ2 (2)] and [link equ3 (3)], which scales the checked difference rather than `epsilon`:
 248
 249 [#equ4]
 250 ``
 251    abs(u - v)/abs(u) <= epsilon
 252 && abs(u - v)/abs(v) <= epsilon; // (4)
 253 ``
 254
 255 [#equ5]
 256 ``
 257    abs(u - v)/abs(u) <= epsilon
 258 || abs(u - v)/abs(v) <= epsilon; // (5)
 259 ``
 260
 261 This way all underflow and overflow conditions can be guarded safely. The above however, will not work when `v` or `u` is zero.
 262 In such cases the solution is to resort to a different algorithm, e.g. [link equ1 (1)].
 263
 264
 265 [h3 Tolerance selection considerations]
 266
 267 In case of absence of domain specific requirements the value of tolerance can be chosen as a sum of the predicted
 268 upper limits for "relative rounding errors" of compared values. The "rounding" is the operation by which a real
 269 value 'x' is represented in a floating-point format with 'p' binary digits (bits) as the floating-point value [*X].
 270 The "relative rounding error" is the difference between the real and the floating point values in relation to real
 271 value: `abs(x-X)/abs(x)`. The discrepancy between real and floating point value may be caused by several reasons:
 272
 273 * Type promotion
 274 * Arithmetic operations
 275 * Conversion from a decimal presentation to a binary presentation
 276 * Non-arithmetic operation
 277
 278
 279 The first two operations proved to have a relative rounding error that does not exceed
 280
 281   half_epsilon = half of the 'machine epsilon value'
 282
 283 for the appropriate floating point type `FPT` [footnote [*machine epsilon value] is represented by `std::numeric_limits<FPT>::epsilon()`].
 284 Conversion to binary presentation, sadly, does not have such requirement. So we can't assume that `float(1.1)` is close
 285 to the real number `1.1` with tolerance `half_epsilon` for float (though for 11./10 we can). Non-arithmetic operations either do not have a
 286 predicted upper limit relative rounding errors.
 287
 288 [note Note that both arithmetic and non-arithmetic operations might also
 289 produce others "non-rounding" errors, such as underflow/overflow, division-by-zero or "operation errors".]
 290
 291
 292 All theorems about the upper limit of a rounding error, including that of `half_epsilon`, refer only to
 293 the 'rounding' operation, nothing more. This means that the 'operation error', that is, the error incurred by the
 294 operation itself, besides rounding, isn't considered. In order for numerical software to be able to actually
 295 predict error bounds, the __IEEE754__ standard requires arithmetic operations to be 'correctly or exactly rounded'.
 296 That is, it is required that the internal computation of a given operation be such that the floating point result
 297 is the exact result rounded to the number of working bits. In other words, it is required that the computation used
 298 by the operation itself doesn't introduce any additional errors. The __IEEE754__ standard does not require same behavior
 299 from most non-arithmetic operation. The underflow/overflow and division-by-zero errors may cause rounding errors
 300 with unpredictable upper limits.
 301
 302 At last be aware that `half_epsilon` rules are not transitive. In other words combination of two
 303 arithmetic operations may produce rounding error that significantly exceeds `2*half_epsilon`. All
 304 in all there are no generic rules on how to select the tolerance and users need to apply common sense and domain/
 305 problem specific knowledge to decide on tolerance value.
 306
 307 To simplify things in most usage cases latest version of algorithm below opted to use percentage values for
 308 tolerance specification (instead of fractions of related values). In other words now you use it to check that
 309 difference between two values does not exceed x percent.
 310
 311 For more reading about floating-point comparison see references below.
 312
 313 [h4 Bibliographic references]
 314 [variablelist Books
 315   [
 316     [[#KnuthII]The art of computer programming (vol II)]
 317     [Donald. E. Knuth, 1998, Addison-Wesley Longman, Inc., ISBN 0-201-89684-2, Addison-Wesley Professional; 3rd edition.
 318      (The relevant equations are in §4.2.2, Eq. 36 and 37.)]
 319   ]
 320   [
 321     [Rounding near zero, in [@http://www.amazon.com/Advanced-Arithmetic-Digital-Computer-Kulisch/dp/3211838708 Advanced Arithmetic for the Digital Computer]]
 322     [Ulrich W. Kulisch, 2002, Springer, Inc., ISBN 0-201-89684-2, Springer; 1st edition]
 323   ]
 324 ]
 325
 326 [variablelist Periodicals
 327   [
 328     [[#Squassabia][@https://adtmag.com/articles/2000/03/16/comparing-floats-how-to-determine-if-floating-quantities-are-close-enough-once-a-tolerance-has-been.aspx
 329       Comparing Floats: How To Determine if Floating Quantities Are Close Enough Once a Tolerance Has Been Reached]]
 330     [Alberto Squassabia, in C++ Report (March 2000)]
 331   ]
 332
 333   [
 334     [The Journeyman's Shop: Trap Handlers, Sticky Bits, and Floating-Point Comparisons]
 335     [Pete Becker, in C/C++ Users Journal (December 2000)]
 336   ]
 337 ]
 338
 339 [variablelist Publications
 340   [
 341     [[@http://dl.acm.org/citation.cfm?id=103163
 342       What Every Computer Scientist Should Know About Floating-Point Arithmetic]]
 343     [David Goldberg, pages 150-230, in Computing Surveys (March 1991), Association for Computing Machinery, Inc.]
 344   ]
 345
 346   [
 347     [[@http://hal.archives-ouvertes.fr/docs/00/07/26/81/PDF/RR-3967.pdf From Rounding Error Estimation to Automatic Correction with Automatic Differentiation]]
 348     [Philippe Langlois, Technical report, INRIA]
 349   ]
 350
 351   [
 352     [[@http://www.cs.berkeley.edu/~wkahan/
 353       William Kahan home page]]
 354     [Lots of information on floating point arithmetics.]
 355   ]
 356
 357 ]
 358
 359 [endsect] [/ theory]
 360
 361 [endsect] [/ floating points]