third_party/rust/float-cmp/README.md

   1 # float-cmp
   2
   3 [![Build Status](https://travis-ci.org/mikedilger/float-cmp.svg?branch=master)](https://travis-ci.org/mikedilger/float-cmp)
   4 [![MIT licensed](https://img.shields.io/badge/license-MIT-blue.svg)](./LICENSE)
   5
   6 Documentation is available at https://docs.rs/float-cmp
   7
   8 float-cmp defines and implements traits for approximate comparison of floating point types
   9 which have fallen away from exact equality due to the limited precision available within
  10 floating point representations. Implementations of these traits are provided for `f32`
  11 and `f64` types.
  12
  13 When I was a kid in the '80s, the programming rule was "Never compare floating point
  14 numbers". If you can follow that rule and still get the outcome you desire, then more
  15 power to you. However, if you really do need to compare them, this crate provides a
  16 reasonable way to do so.
  17
  18 Another crate `efloat` offers another solution by providing a floating point type that
  19 tracks its error bounds as operations are performed on it, and thus can implement the
  20 `ApproxEq` trait in this crate more accurately, without specifying a `Margin`.
  21
  22 The recommended go-to solution (although it may not be appropriate in all cases) is the
  23 `approx_eq()` function in the `ApproxEq` trait (or better yet, the macros).  For `f32`
  24 and `f64`, the `F32Margin` and `F64Margin` types are provided for specifying margins as
  25 both an epsilon value and an ULPs value, and defaults are provided via `Default`
  26 (although there is no perfect default value that is always appropriate, so beware).
  27
  28 Several other traits are provided including `Ulps`, `ApproxEqUlps`, `ApproxOrdUlps`, and
  29 `ApproxEqRatio`.
  30
  31 ## The problem
  32
  33 Floating point operations must round answers to the nearest representable number. Multiple
  34 operations may result in an answer different from what you expect. In the following example,
  35 the assert will fail, even though the printed output says "0.45 == 0.45":
  36
  37 ```rust
  38   let a: f32 = 0.15 + 0.15 + 0.15;
  39   let b: f32 = 0.1 + 0.1 + 0.25;
  40   println!("{} == {}", a, b);
  41   assert!(a==b)  // Fails, because they are not exactly equal
  42 ```
  43
  44 This fails because the correct answer to most operations isn't exactly representable, and so
  45 your computer's processor chooses to represent the answer with the closest value it has
  46 available. This introduces error, and this error can accumulate as multiple operations are
  47 performed.
  48
  49 ## The solution
  50
  51 With `ApproxEq`, we can get the answer we intend:
  52 ```rust
  53   let a: f32 = 0.15 + 0.15 + 0.15;
  54   let b: f32 = 0.1 + 0.1 + 0.25;
  55   println!("{} == {}", a, b);
  56   assert!( approx_eq!(f32, a, b, ulps = 2) );
  57 ```
  58
  59 ## Some explanation
  60
  61 We use the term ULP (units of least precision, or units in the last place) to mean the
  62 difference between two adjacent floating point representations (adjacent meaning that there is
  63 no floating point number between them). This term is borrowed from prior work (personally I
  64 would have chosen "quanta"). The size of an ULP (measured as a float) varies
  65 depending on the exponents of the floating point numbers in question. That is a good thing,
  66 because as numbers fall away from equality due to the imprecise nature of their representation,
  67 they fall away in ULPs terms, not in absolute terms.  Pure epsilon-based comparisons are
  68 absolute and thus don't map well to the nature of the additive error issue. They work fine
  69 for many ranges of numbers, but not for others (consider comparing -0.0000000028
  70 to +0.00000097).
  71
  72 ## Using this crate
  73
  74 You can use the `ApproxEq` trait directly like so:
  75
  76 ```rust
  77     assert!( a.approx_eq(b, F32Margin { ulps: 2, epsilon: 0.0 }) );
  78 ```
  79
  80 We have implemented `From<(f32,i32)>` for `F32Margin` (and similarly for `F64Margin`)
  81 so you can use this shorthand:
  82
  83 ```rust
  84     assert!( a.approx_eq(b, (0.0, 2)) );
  85 ```
  86
  87 With macros, it is easier to be explicit about which type of margin you wish to set,
  88 without mentioning the other one (the other one will be zero). But the downside is
  89 that you have to specify the type you are dealing with:
  90
  91 ```rust
  92     assert!( approx_eq!(f32, a, b, ulps = 2) );
  93     assert!( approx_eq!(f32, a, b, epsilon = 0.00000003) );
  94     assert!( approx_eq!(f32, a, b, epsilon = 0.00000003, ulps = 2) );
  95     assert!( approx_eq!(f32, a, b, (0.0, 2)) );
  96     assert!( approx_eq!(f32, a, b, F32Margin { epsilon: 0.0, ulps: 2 }) );
  97     assert!( approx_eq!(f32, a, b, F32Margin::default()) );
  98     assert!( approx_eq!(f32, a, b) ); // uses the default
  99 ```
 100
 101 For most cases, I recommend you use a smallish integer for the `ulps` parameter (1 to 5
 102 or so), and a similar small multiple of the floating point's EPSILON constant (1.0 to 5.0
 103 or so), but there are *plenty* of cases where this is insufficient.
 104
 105 ## Implementing these traits
 106
 107 You can implement `ApproxEq` for your own complex types like shown below.
 108 The floating point type `F` must be `Copy`, but for large types you can implement
 109 it for references to your type as shown.
 110
 111 ```rust
 112 use float_cmp::ApproxEq;
 113
 114 pub struct Vec2<F> {
 115   pub x: F,
 116   pub y: F,
 117 }
 118
 119 impl<'a, M: Copy, F: Copy + ApproxEq<Margin=M>> ApproxEq for &'a Vec2<F> {
 120   type Margin = M;
 121
 122    fn approx_eq<T: Into<Self::Margin>>(self, other: Self, margin: T) -> bool {
 123      let margin = margin.into();
 124      self.x.approx_eq(other.x, margin)
 125        && self.y.approx_eq(other.y, margin)
 126    }
 127 }
 128 ```
 129
 130 ## Non floating-point types
 131
 132 `ApproxEq` can be implemented for non floating-point types as well, since `Margin` is
 133 an associated type.
 134
 135 The `efloat` crate implements (or soon will implement) `ApproxEq` for a compound type
 136 that tracks floating point error bounds by checking if the error bounds overlap.
 137 In that case `type Margin = ()`.
 138
 139 ## Inspiration
 140
 141 This crate was inspired by this Random ASCII blog post:
 142
 143 [https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/](https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/)