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