]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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] |