Home > The Unit Test Framework > Testing tools > Floating-point comparison algorithms
PrevNext

本章數學性太強,翻譯很差強人意,希望哪位大牛能夠指正 -- 譯者注

Floating-point comparison algorithms

In most cases it is unreasonable to use an operator==(...) for a floating-point values equality check. The simple, absolute value comparison based, solution for a floating-point values u, v and a tolerance :
在大多數情況下,不應用使用 operator==(...) 來檢查浮點數是否相等。 簡單的,基於絕對值比較的,應用於浮點數值 uv 和限度的解決方案:

|u v|
(1)

does not produce expected results in many circumstances - specifically for very small or very big values (See [Squassabia] for examples). The UTF implements floating-point comparison algorithm that is based on the more confident solution first presented in [KnuthII]:
在很多情況下不能產生期望的結果 - 尤其是對於非常小或非常大的值 (例子參見[Squassabia])。 UTF 實現的浮點數比較算法基於首次出現於 [KnuthII] 的更可靠的解決方案:

|u v| |u| |u v| |v|
(2)

defines a very close with tolerance relationship between u and v
定義了 uv非常接近限度的關係

|u v| |u| |u v| |v|
(3)

defines a close enough with tolerance relationship between u and v
定義了 uv 足夠接受限度的關係

Both relationships are commutative but are not transitive. The relationship defined by inequations (2) is stronger that the relationship defined by inequations (3) (i.e. (2) (3)). Because of the multiplication in the right side of inequations, that can cause an unwanted underflow condition, the implementation is using modified version of the inequations (2) and (3) where all underflow, overflow conditions can be guarded safely:
兩種關係都是可交換的,但不是可傳遞的。 不等式 (2) 定義的關係強於不等式 (3) 定義的關係 (也就是 (2) (3))。 因為不等式右邊的乘法可能會引起不期望的下溢條件, 實現使用修改版的不等式 (2) 和 (3), 所有下溢,上溢的條件都被安全地監視:

|u v| |u| |u v| / |v|
(4)
|u v| |u| |u v| / |v|
(5)

Checks based on equations (4) and (5) are implemented by two predicates with alternative interfaces: binary predicate close_at_tolerance[8] and predicate with four arguments check_is_close[9].
基於不等式 (4) 和 (5) 的檢查由可選接口的兩個斷言實現: 二元謂詞 close_at_tolerance[8] 和接受四個參數的謂詞 check_is_close[9]

While equations (4) and (5) in general are preferred for the general floating point comparison check over equation (1), they are unusable for the test on closeness to zero. The later check is still might be useful in some cases and the UTF implements an algorithm based on equation (1) in binary predicate check_is_small[10].
相對於等式 (1),雖然在通常情況下,不等式 (4) 和 (5) 是通用浮點數比較檢查的首先,但在測試接近於 0 的時候是不安全的。 前一個檢查在某些情況下仍然是有用的,基於等式 (1) UTF 實現了二元謂詞 check_is_small[10]

On top of the generic, flexible predicates the UTF implements macro based family of tools BOOST_CHECK_CLOSE and BOOST_CHECK_SMALL. These tools limit the check flexibility to strong-only checks, but automate failed check arguments reporting.
在通用、可伸縮的謂詞基礎上,UTF 實現了基於宏的工具族 BOOST_CHECK_CLOSEBOOST_CHECK_SMALL。 這些工具將檢查的可伸縮性限制為只關注健壯性的檢查,但自動報告失敗的檢查參數。

Tolerance selection considerations

In case of absence of domain specific requirements the value of tolerance can be chosen as a sum of the predicted upper limits for "relative rounding errors" of compared values. The "rounding" is the operation by which a real value 'x' is represented in a floating-point format with 'p' binary digits (bits) as the floating-point value 'X'. The "relative rounding error" is the difference between the real and the floating point values in relation to real value: |x-X|/|x|. The discrepancy between real and floating point value may be caused by several reasons:
假設存在領域特定需求,限度的值可被選為要比較值的 "相對捨入誤差" 的可預測上限的總和。 "捨入" 是將實數 'x' 被以浮點數格式用 'p' 二進制進 (位) 表示的浮點數 'X'。(???) "相對捨入誤差" 是實數和浮點數值在關係 |x-X|/|x| 的差值。 實數和浮點數值之間的差異可能由如下原因引起:

  • Type promotion 類型提升
  • Arithmetic operations 算術操作
  • Conversion from a decimal presentation to a binary presentation 十進製表示轉換為二進製表示
  • Non-arithmetic operation 非算術操作

The first two operations proved to have a relative rounding error that does not exceed "machine epsilon value" for the appropriate floating point type (represented by std::numeric_limits<FPT>::epsilon()). Conversion to binary presentation, sadly, does not have such requirement. So we can't assume that float 1.1 is close to real 1.1 with tolerance "machine epsilon value" for float (though for 11./10 we can). Non arithmetic operations either do not have a predicted upper limit relative rounding errors. Note that both arithmetic and non-arithmetic operations might also produce others "non-rounding" errors, such as underflow/overflow, division-by-zero or 'operation errors'.
前兩個操作被證明有不超過相應浮點數類型 "機器精度值" (用 std::numeric_limits<FPT>::epsilon() 表示) 的相對捨入誤差。 不幸的是,轉換為二進製表示,沒有這樣的保證。 所以我們不能假定浮點數 1.1 在浮點數 "機器精度值" 的限度上接近實數 1.1 (雖然對於 11./10 我們可以這麼說)。 非算術操作也沒有可預料上限的相對捨入誤差。 注意,算術操作和非算術操作都可能產生其它 "非捨入" 誤差,例如下溢 / 上溢,除 0,或 '操作誤差'。

All theorems about the upper limit of a rounding error, including that of epsilon, refer only to the 'rounding' operation, nothing more. This means that the 'operation error', that is, the error incurred by the operation itself, besides rounding, isn't considered. In order for numerical software to be able to actually predict error bounds, the IEEE754 standard requires arithmetic operations to be 'correctly or exactly rounded'. That is, it is required that the internal computation of a given operation be such that the floating point result is the exact result rounded to the number of working bits. In other words, it is required that the computation used by the operation itself doesn't introduce any additional errors. The IEEE754 standard does not require same behavior from most non-arithmetic operation. The underflow/overflow and division-by-zero errors may cause rounding errors with unpredictable upper limits.
關於捨入誤差上限,包括精度的所有理論,都只考慮 '捨入' 操作,不考慮其它。 這意味著 '操作誤差',即操作本身產生的誤差,包括捨入,並沒有考慮在內。 對於數值計算軟件,為了得到實際可預料的誤差範圍,IEEE754 標準要求算術操作是 '正確或精確捨入' 的。 也就是說,它要求給定操作的內部計算的浮點結果是工作位的精確四捨五入結果。 換句話說,要求計算本身的操作不引入額外的誤差。IEEE754 標準並不要求大多數非算術操作有相同的行為。 下溢/上溢和除 0 錯誤可能引起不可預料上限的捨入誤差。

At last be aware that epsilon rules are not transitive. In other words combination of two arithmetic operations may produce rounding error that significantly exceeds 2 epsilon. All in all there are no generic rules on how to select the tolerance and users need to apply common sense and domain/ problem specific knowledge to decide on tolerance value.
最後注意精度原則不是傳遞的。換句話說,兩個操作操作的組合可能會產生顯著超過 2 倍精度的誤差。 總之,沒有如何選擇限度的通用準則,用戶需要根據通用認識和領域 / 問題特定知識決定限度值。

To simplify things in most usage cases latest version of algorithm below opted to use percentage values for tolerance specification (instead of fractions of related values). In other words now you use it to check that difference between two values does not exceed x percent.
為了在多數情況下簡化問題,下面最後一片算法選擇使用百分比值作為限度 (而不是相關數值的分數)。 換句話說,你現在使用它檢查兩個值差距不超過 x 百分比。

For more reading about floating-point comparison see references below.
更多關於浮點數比較的著作請參見下面的參考。

A floating-point comparison related references

Books

[KnuthII] The art of computer programming (vol II). Donald. E. Knuth. Copyright c 1998 Addison-Wesley Longman, Inc.. 0-201-89684-2. Addison-Wesley Professional; 3 edition.

[Kulisch] Rounding near zero. Advanced Arithmetic for the Digital Computer. Ulrich W Kulisch. Copyright c 2002 Springer, Inc.. 0-201-89684-2. Springer; 1 edition.

Periodicals

[Becker] 「The Journeyman's Shop: Trap Handlers, Sticky Bits, and Floating-Point Comparisons」. Pete Becker. C/C++ Users Journal. December 2000. .

Publications

[Goldberg] What Every Computer Scientist Should Know About Floating-Point Arithmetic」. David Goldberg. Copyright c 1991 Association for Computing Machinery, Inc.. 150-230. Computing Surveys. March. .

[Langlois] From Rounding Error Estimation to Automatic Correction with Automatic Differentiation. Philippe Langlois. Copyright c 2000. 0249-6399.



[8] check type and tolerance value are fixed at predicate construction time

[9] check type and tolerance value are the arguments of the predicate

[10] v is zero


PrevUpHomeNext