diff options
Diffstat (limited to 'third_party/rust/float-cmp')
| -rw-r--r-- | third_party/rust/float-cmp/.cargo-checksum.json | 1 | ||||
| -rw-r--r-- | third_party/rust/float-cmp/Cargo.toml | 37 | ||||
| -rw-r--r-- | third_party/rust/float-cmp/LICENSE | 19 | ||||
| -rw-r--r-- | third_party/rust/float-cmp/README.md | 143 | ||||
| -rw-r--r-- | third_party/rust/float-cmp/src/eq.rs | 284 | ||||
| -rw-r--r-- | third_party/rust/float-cmp/src/lib.rs | 196 | ||||
| -rw-r--r-- | third_party/rust/float-cmp/src/macros.rs | 77 | ||||
| -rw-r--r-- | third_party/rust/float-cmp/src/ratio.rs | 142 | ||||
| -rw-r--r-- | third_party/rust/float-cmp/src/ulps.rs | 240 | ||||
| -rw-r--r-- | third_party/rust/float-cmp/src/ulps_eq.rs | 119 |
10 files changed, 1258 insertions, 0 deletions
diff --git a/third_party/rust/float-cmp/.cargo-checksum.json b/third_party/rust/float-cmp/.cargo-checksum.json new file mode 100644 index 0000000000..64b9f03303 --- /dev/null +++ b/third_party/rust/float-cmp/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.toml":"9dbf5b8451e618eaccd9c9e9360042f8e9aa1db0f05df9300e2b677a9393eff4","LICENSE":"0b4228e50c57acadaef1e9c39eb4494abe91b312088a8d1744ddf1a50310a915","README.md":"3dc6976c44ce23c76f38a9834b0cd3c4bd1d2103a7c3bcf71517b9722c07aae7","src/eq.rs":"44197a5635757405c59b3870fb4741bd2425a16be9a92657bd24adbb0ac7f7df","src/lib.rs":"ef87d7668ffa8bd4f80654871e1108b2e75b176fcd97b66dca0ef6924595cbe4","src/macros.rs":"85f7d267aee869b5a3c97727f6a6b66848ea3adcf7ea1f4ea0e3626264b216d0","src/ratio.rs":"4c097204d91a20346fcf1e44b94cb116bb6ee130517d29635ade58ddea08750e","src/ulps.rs":"bfea6ab54c98c8337c76c9efd50cbd4ba911ebc146c9b6cfa2952fc55740f01b","src/ulps_eq.rs":"28ff2086c0c11ddfbb40c5b4d5aa3f0c3f4d399137ee37c71a24e8e106b866d4"},"package":"da62c4f1b81918835a8c6a484a397775fff5953fe83529afd51b05f5c6a6617d"}
\ No newline at end of file diff --git a/third_party/rust/float-cmp/Cargo.toml b/third_party/rust/float-cmp/Cargo.toml new file mode 100644 index 0000000000..e3b9449603 --- /dev/null +++ b/third_party/rust/float-cmp/Cargo.toml @@ -0,0 +1,37 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies +# +# If you believe there's an error in this file please file an +# issue against the rust-lang/cargo repository. If you're +# editing this file be aware that the upstream Cargo.toml +# will likely look very different (and much more reasonable) + +[package] +edition = "2018" +name = "float-cmp" +version = "0.6.0" +authors = ["Mike Dilger <mike@mikedilger.com>"] +description = "Floating point approximate comparison traits" +documentation = "https://docs.rs/float-cmp" +readme = "README.md" +keywords = ["float", "comparison", "fuzzy", "approximate"] +license = "MIT" +repository = "https://github.com/mikedilger/float-cmp" + +[lib] +name = "float_cmp" +path = "src/lib.rs" +test = true +doctest = true +doc = true +[dependencies.num-traits] +version = "0.2" +optional = true +default-features = false + +[features] +default = ["num-traits"] diff --git a/third_party/rust/float-cmp/LICENSE b/third_party/rust/float-cmp/LICENSE new file mode 100644 index 0000000000..75ad606734 --- /dev/null +++ b/third_party/rust/float-cmp/LICENSE @@ -0,0 +1,19 @@ +Copyright (c) 2014-2018 Optimal Computing (NZ) Ltd + +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies +of the Software, and to permit persons to whom the Software is furnished to do +so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +IN THE SOFTWARE. diff --git a/third_party/rust/float-cmp/README.md b/third_party/rust/float-cmp/README.md new file mode 100644 index 0000000000..79949804ea --- /dev/null +++ b/third_party/rust/float-cmp/README.md @@ -0,0 +1,143 @@ +# float-cmp + +[](https://travis-ci.org/mikedilger/float-cmp) +[](./LICENSE) + +Documentation is available at https://docs.rs/float-cmp + +float-cmp defines and implements traits for approximate comparison of floating point types +which have fallen away from exact equality due to the limited precision available within +floating point representations. Implementations of these traits are provided for `f32` +and `f64` types. + +When I was a kid in the '80s, the programming rule was "Never compare floating point +numbers". If you can follow that rule and still get the outcome you desire, then more +power to you. However, if you really do need to compare them, this crate provides a +reasonable way to do so. + +Another crate `efloat` offers another solution by providing a floating point type that +tracks its error bounds as operations are performed on it, and thus can implement the +`ApproxEq` trait in this crate more accurately, without specifying a `Margin`. + +The recommended go-to solution (although it may not be appropriate in all cases) is the +`approx_eq()` function in the `ApproxEq` trait (or better yet, the macros). For `f32` +and `f64`, the `F32Margin` and `F64Margin` types are provided for specifying margins as +both an epsilon value and an ULPs value, and defaults are provided via `Default` +(although there is no perfect default value that is always appropriate, so beware). + +Several other traits are provided including `Ulps`, `ApproxEqUlps`, `ApproxOrdUlps`, and +`ApproxEqRatio`. + +## The problem + +Floating point operations must round answers to the nearest representable number. Multiple +operations may result in an answer different from what you expect. In the following example, +the assert will fail, even though the printed output says "0.45 == 0.45": + +```rust + let a: f32 = 0.15 + 0.15 + 0.15; + let b: f32 = 0.1 + 0.1 + 0.25; + println!("{} == {}", a, b); + assert!(a==b) // Fails, because they are not exactly equal +``` + +This fails because the correct answer to most operations isn't exactly representable, and so +your computer's processor chooses to represent the answer with the closest value it has +available. This introduces error, and this error can accumulate as multiple operations are +performed. + +## The solution + +With `ApproxEq`, we can get the answer we intend: +```rust + let a: f32 = 0.15 + 0.15 + 0.15; + let b: f32 = 0.1 + 0.1 + 0.25; + println!("{} == {}", a, b); + assert!( approx_eq!(f32, a, b, ulps = 2) ); +``` + +## Some explanation + +We use the term ULP (units of least precision, or units in the last place) to mean the +difference between two adjacent floating point representations (adjacent meaning that there is +no floating point number between them). This term is borrowed from prior work (personally I +would have chosen "quanta"). The size of an ULP (measured as a float) varies +depending on the exponents of the floating point numbers in question. That is a good thing, +because as numbers fall away from equality due to the imprecise nature of their representation, +they fall away in ULPs terms, not in absolute terms. Pure epsilon-based comparisons are +absolute and thus don't map well to the nature of the additive error issue. They work fine +for many ranges of numbers, but not for others (consider comparing -0.0000000028 +to +0.00000097). + +## Using this crate + +You can use the `ApproxEq` trait directly like so: + +```rust + assert!( a.approx_eq(b, F32Margin { ulps: 2, epsilon: 0.0 }) ); +``` + +We have implemented `From<(f32,i32)>` for `F32Margin` (and similarly for `F64Margin`) +so you can use this shorthand: + +```rust + assert!( a.approx_eq(b, (0.0, 2)) ); +``` + +With macros, it is easier to be explicit about which type of margin you wish to set, +without mentioning the other one (the other one will be zero). But the downside is +that you have to specify the type you are dealing with: + +```rust + assert!( approx_eq!(f32, a, b, ulps = 2) ); + assert!( approx_eq!(f32, a, b, epsilon = 0.00000003) ); + assert!( approx_eq!(f32, a, b, epsilon = 0.00000003, ulps = 2) ); + assert!( approx_eq!(f32, a, b, (0.0, 2)) ); + assert!( approx_eq!(f32, a, b, F32Margin { epsilon: 0.0, ulps: 2 }) ); + assert!( approx_eq!(f32, a, b, F32Margin::default()) ); + assert!( approx_eq!(f32, a, b) ); // uses the default +``` + +For most cases, I recommend you use a smallish integer for the `ulps` parameter (1 to 5 +or so), and a similar small multiple of the floating point's EPSILON constant (1.0 to 5.0 +or so), but there are *plenty* of cases where this is insufficient. + +## Implementing these traits + +You can implement `ApproxEq` for your own complex types like shown below. +The floating point type `F` must be `Copy`, but for large types you can implement +it for references to your type as shown. + +```rust +use float_cmp::ApproxEq; + +pub struct Vec2<F> { + pub x: F, + pub y: F, +} + +impl<'a, M: Copy, F: Copy + ApproxEq<Margin=M>> ApproxEq for &'a Vec2<F> { + type Margin = M; + + fn approx_eq<T: Into<Self::Margin>>(self, other: Self, margin: T) -> bool { + let margin = margin.into(); + self.x.approx_eq(other.x, margin) + && self.y.approx_eq(other.y, margin) + } +} +``` + +## Non floating-point types + +`ApproxEq` can be implemented for non floating-point types as well, since `Margin` is +an associated type. + +The `efloat` crate implements (or soon will implement) `ApproxEq` for a compound type +that tracks floating point error bounds by checking if the error bounds overlap. +In that case `type Margin = ()`. + +## Inspiration + +This crate was inspired by this Random ASCII blog post: + +[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/) diff --git a/third_party/rust/float-cmp/src/eq.rs b/third_party/rust/float-cmp/src/eq.rs new file mode 100644 index 0000000000..d39535c95a --- /dev/null +++ b/third_party/rust/float-cmp/src/eq.rs @@ -0,0 +1,284 @@ +// Copyright 2014-2018 Optimal Computing (NZ) Ltd. +// Licensed under the MIT license. See LICENSE for details. + +use std::{f32,f64}; +use super::Ulps; + +/// ApproxEq is a trait for approximate equality comparisons. +pub trait ApproxEq: Sized { + /// The Margin type defines a margin within which two values are to be + /// considered approximately equal. It must implement Default so that + /// approx_eq() can be called on unknown types. + type Margin: Copy + Default; + + /// This method tests for `self` and `other` values to be approximately equal + /// within `margin`. + fn approx_eq<M: Into<Self::Margin>>(self, other: Self, margin: M) -> bool; + + /// This method tests for `self` and `other` values to be not approximately + /// equal within `margin`. + fn approx_ne<M: Into<Self::Margin>>(self, other: Self, margin: M) -> bool { + !self.approx_eq(other, margin) + } +} + +/// This type defines a margin within two f32s might be considered equal +/// and is intended as the associated type for the `ApproxEq` trait. +/// +/// Two methods are used to determine approximate equality. +/// +/// First an epsilon method is used, considering them approximately equal if they +/// differ by <= `epsilon`. This will only succeed for very small numbers. +/// Note that it may succeed even if the parameters are of differing signs straddling +/// zero. +/// +/// The second method considers how many ULPs (units of least precision, units in +/// the last place, which is the integer number of floating point representations +/// that the parameters are separated by) different the parameters are and considers +/// them approximately equal if this is <= `ulps`. For large floating point numbers, +/// an ULP can be a rather large gap, but this kind of comparison is necessary +/// because floating point operations must round to the nearest representable value +/// and so larger floating point values accumulate larger errors. +#[repr(C)] +#[derive(Debug, Clone, Copy)] +pub struct F32Margin { + pub epsilon: f32, + pub ulps: i32 +} +impl Default for F32Margin { + #[inline] + fn default() -> F32Margin { + F32Margin { + epsilon: f32::EPSILON, + ulps: 4 + } + } +} +impl F32Margin { + #[inline] + pub fn zero() -> F32Margin { + F32Margin { + epsilon: 0.0, + ulps: 0 + } + } + pub fn epsilon(self, epsilon: f32) -> Self { + F32Margin { + epsilon: epsilon, + ..self + } + } + pub fn ulps(self, ulps: i32) -> Self { + F32Margin { + ulps: ulps, + ..self + } + } +} +impl From<(f32, i32)> for F32Margin { + fn from(m: (f32, i32)) -> F32Margin { + F32Margin { + epsilon: m.0, + ulps: m.1 + } + } +} + +impl ApproxEq for f32 { + type Margin = F32Margin; + + fn approx_eq<M: Into<Self::Margin>>(self, other: f32, margin: M) -> bool { + let margin = margin.into(); + + // Check for exact equality first. This is often true, and so we get the + // performance benefit of only doing one compare in most cases. + self==other || + + // Perform epsilon comparison next + ((self - other).abs() <= margin.epsilon) || + + { + // Perform ulps comparion last + let diff: i32 = self.ulps(&other); + saturating_abs_i32!(diff) <= margin.ulps + } + } +} + +#[test] +fn f32_approx_eq_test1() { + let f: f32 = 0.0_f32; + let g: f32 = -0.0000000000000005551115123125783_f32; + assert!(f != g); // Should not be directly equal + assert!(f.approx_eq(g, (f32::EPSILON, 0)) == true); +} +#[test] +fn f32_approx_eq_test2() { + let f: f32 = 0.0_f32; + let g: f32 = -0.0_f32; + assert!(f.approx_eq(g, (f32::EPSILON, 0)) == true); +} +#[test] +fn f32_approx_eq_test3() { + let f: f32 = 0.0_f32; + let g: f32 = 0.00000000000000001_f32; + assert!(f.approx_eq(g, (f32::EPSILON, 0)) == true); +} +#[test] +fn f32_approx_eq_test4() { + let f: f32 = 0.00001_f32; + let g: f32 = 0.00000000000000001_f32; + assert!(f.approx_eq(g, (f32::EPSILON, 0)) == false); +} +#[test] +fn f32_approx_eq_test5() { + let f: f32 = 0.1_f32; + let mut sum: f32 = 0.0_f32; + for _ in 0_isize..10_isize { sum += f; } + let product: f32 = f * 10.0_f32; + assert!(sum != product); // Should not be directly equal: + println!("Ulps Difference: {}",sum.ulps(&product)); + assert!(sum.approx_eq(product, (f32::EPSILON, 1)) == true); + assert!(sum.approx_eq(product, F32Margin::zero()) == false); +} +#[test] +fn f32_approx_eq_test6() { + let x: f32 = 1000000_f32; + let y: f32 = 1000000.1_f32; + assert!(x != y); // Should not be directly equal + assert!(x.approx_eq(y, (0.0, 2)) == true); // 2 ulps does it + // epsilon method no good here: + assert!(x.approx_eq(y, (1000.0 * f32::EPSILON, 0)) == false); +} + +/// This type defines a margin within two f32s might be considered equal +/// and is intended as the associated type for the `ApproxEq` trait. +/// +/// Two methods are used to determine approximate equality. +/// +/// First an epsilon method is used, considering them approximately equal if they +/// differ by <= `epsilon`. This will only succeed for very small numbers. +/// Note that it may succeed even if the parameters are of differing signs straddling +/// zero. +/// +/// The second method considers how many ULPs (units of least precision, units in +/// the last place, which is the integer number of floating point representations +/// that the parameters are separated by) different the parameters are and considers +/// them approximately equal if this <= `ulps`. For large floating point numbers, +/// an ULP can be a rather large gap, but this kind of comparison is necessary +/// because floating point operations must round to the nearest representable value +/// and so larger floating point values accumulate larger errors. +#[derive(Debug, Clone, Copy)] +pub struct F64Margin { + pub epsilon: f64, + pub ulps: i64 +} +impl Default for F64Margin { + #[inline] + fn default() -> F64Margin { + F64Margin { + epsilon: f64::EPSILON, + ulps: 4 + } + } +} +impl F64Margin { + #[inline] + pub fn zero() -> F64Margin { + F64Margin { + epsilon: 0.0, + ulps: 0 + } + } + pub fn epsilon(self, epsilon: f64) -> Self { + F64Margin { + epsilon: epsilon, + ..self + } + } + pub fn ulps(self, ulps: i64) -> Self { + F64Margin { + ulps: ulps, + ..self + } + } +} +impl From<(f64, i64)> for F64Margin { + fn from(m: (f64, i64)) -> F64Margin { + F64Margin { + epsilon: m.0, + ulps: m.1 + } + } +} + +impl ApproxEq for f64 { + type Margin = F64Margin; + + fn approx_eq<M: Into<Self::Margin>>(self, other: f64, margin: M) -> bool { + let margin = margin.into(); + + // Check for exact equality first. This is often true, and so we get the + // performance benefit of only doing one compare in most cases. + self==other || + + // Perform epsilon comparison next + ((self - other).abs() <= margin.epsilon) || + + { + // Perform ulps comparion last + let diff: i64 = self.ulps(&other); + saturating_abs_i64!(diff) <= margin.ulps + } + } +} + +#[test] +fn f64_approx_eq_test1() { + let f: f64 = 0.0_f64; + let g: f64 = -0.0000000000000005551115123125783_f64; + assert!(f != g); // Should not be directly equal + assert!(f.approx_eq(g, (3.0 * f64::EPSILON, 0)) == true); // 3e is enough + // ulps test wont ever call these equal +} +#[test] +fn f64_approx_eq_test2() { + let f: f64 = 0.0_f64; + let g: f64 = -0.0_f64; + assert!(f.approx_eq(g, (f64::EPSILON, 0)) == true); +} +#[test] +fn f64_approx_eq_test3() { + let f: f64 = 0.0_f64; + let g: f64 = 1e-17_f64; + assert!(f.approx_eq(g, (f64::EPSILON, 0)) == true); +} +#[test] +fn f64_approx_eq_test4() { + let f: f64 = 0.00001_f64; + let g: f64 = 0.00000000000000001_f64; + assert!(f.approx_eq(g, (f64::EPSILON, 0)) == false); +} +#[test] +fn f64_approx_eq_test5() { + let f: f64 = 0.1_f64; + let mut sum: f64 = 0.0_f64; + for _ in 0_isize..10_isize { sum += f; } + let product: f64 = f * 10.0_f64; + assert!(sum != product); // Should not be directly equal: + println!("Ulps Difference: {}",sum.ulps(&product)); + assert!(sum.approx_eq(product, (f64::EPSILON, 0)) == true); + assert!(sum.approx_eq(product, (0.0, 1)) == true); +} +#[test] +fn f64_approx_eq_test6() { + let x: f64 = 1000000_f64; + let y: f64 = 1000000.0000000003_f64; + assert!(x != y); // Should not be directly equal + println!("Ulps Difference: {}",x.ulps(&y)); + assert!(x.approx_eq(y, (0.0, 3)) == true); +} +#[test] +fn f64_code_triggering_issue_20() { + assert_eq!((-25.0f64).approx_eq(25.0, (0.00390625, 1)), false); +} diff --git a/third_party/rust/float-cmp/src/lib.rs b/third_party/rust/float-cmp/src/lib.rs new file mode 100644 index 0000000000..16ad9d1cef --- /dev/null +++ b/third_party/rust/float-cmp/src/lib.rs @@ -0,0 +1,196 @@ +// Copyright 2014-2018 Optimal Computing (NZ) Ltd. +// Licensed under the MIT license. See LICENSE for details. + +//! # float-cmp +//! +//! float-cmp defines and implements traits for approximate comparison of floating point types +//! which have fallen away from exact equality due to the limited precision available within +//! floating point representations. Implementations of these traits are provided for `f32` +//! and `f64` types. +//! +//! When I was a kid in the '80s, the programming rule was "Never compare floating point +//! numbers". If you can follow that rule and still get the outcome you desire, then more +//! power to you. However, if you really do need to compare them, this crate provides a +//! reasonable way to do so. +//! +//! Another crate `efloat` offers another solution by providing a floating point type that +//! tracks its error bounds as operations are performed on it, and thus can implement the +//! `ApproxEq` trait in this crate more accurately, without specifying a `Margin`. +//! +//! The recommended go-to solution (although it may not be appropriate in all cases) is the +//! `approx_eq()` function in the `ApproxEq` trait (or better yet, the macros). For `f32` +//! and `f64`, the `F32Margin` and `F64Margin` types are provided for specifying margins as +//! both an epsilon value and an ULPs value, and defaults are provided via `Default` +//! (although there is no perfect default value that is always appropriate, so beware). +//! +//! Several other traits are provided including `Ulps`, `ApproxEqUlps`, `ApproxOrdUlps`, and +//! `ApproxEqRatio`. +//! +//! ## The problem +//! +//! Floating point operations must round answers to the nearest representable number. Multiple +//! operations may result in an answer different from what you expect. In the following example, +//! the assert will fail, even though the printed output says "0.45 == 0.45": +//! +//! ```should_panic +//! # extern crate float_cmp; +//! # use float_cmp::ApproxEq; +//! # fn main() { +//! let a: f32 = 0.15 + 0.15 + 0.15; +//! let b: f32 = 0.1 + 0.1 + 0.25; +//! println!("{} == {}", a, b); +//! assert!(a==b) // Fails, because they are not exactly equal +//! # } +//! ``` +//! +//! This fails because the correct answer to most operations isn't exactly representable, and so +//! your computer's processor chooses to represent the answer with the closest value it has +//! available. This introduces error, and this error can accumulate as multiple operations are +//! performed. +//! +//! ## The solution +//! +//! With `ApproxEq`, we can get the answer we intend: +//! +//! ``` +//! # #[macro_use] +//! # extern crate float_cmp; +//! # use float_cmp::{ApproxEq, F32Margin}; +//! # fn main() { +//! let a: f32 = 0.15 + 0.15 + 0.15; +//! let b: f32 = 0.1 + 0.1 + 0.25; +//! println!("{} == {}", a, b); +//! // They are equal, within 2 ulps +//! assert!( approx_eq!(f32, a, b, ulps = 2) ); +//! # } +//! ``` +//! +//! ## Some explanation +//! +//! We use the term ULP (units of least precision, or units in the last place) to mean the +//! difference between two adjacent floating point representations (adjacent meaning that there is +//! no floating point number between them). This term is borrowed from prior work (personally I +//! would have chosen "quanta"). The size of an ULP (measured as a float) varies +//! depending on the exponents of the floating point numbers in question. That is a good thing, +//! because as numbers fall away from equality due to the imprecise nature of their representation, +//! they fall away in ULPs terms, not in absolute terms. Pure epsilon-based comparisons are +//! absolute and thus don't map well to the nature of the additive error issue. They work fine +//! for many ranges of numbers, but not for others (consider comparing -0.0000000028 +//! to +0.00000097). +//! +//! ## Using this crate +//! +//! You can use the `ApproxEq` trait directly like so: +//! +//! ``` +//! # extern crate float_cmp; +//! # use float_cmp::{ApproxEq, F32Margin}; +//! # fn main() { +//! # let a: f32 = 0.15 + 0.15 + 0.15; +//! # let b: f32 = 0.1 + 0.1 + 0.25; +//! assert!( a.approx_eq(b, F32Margin { ulps: 2, epsilon: 0.0 }) ); +//! # } +//! ``` +//! +//! We have implemented `From<(f32,i32)>` for `F32Margin` (and similarly for `F64Margin`) +//! so you can use this shorthand: +//! +//! ``` +//! # extern crate float_cmp; +//! # use float_cmp::{ApproxEq, F32Margin}; +//! # fn main() { +//! # let a: f32 = 0.15 + 0.15 + 0.15; +//! # let b: f32 = 0.1 + 0.1 + 0.25; +//! assert!( a.approx_eq(b, (0.0, 2)) ); +//! # } +//! ``` +//! +//! With macros, it is easier to be explicit about which type of margin you wish to set, +//! without mentioning the other one (the other one will be zero). But the downside is +//! that you have to specify the type you are dealing with: +//! +//! ``` +//! # #[macro_use] +//! # extern crate float_cmp; +//! # use float_cmp::{ApproxEq, F32Margin}; +//! # fn main() { +//! # let a: f32 = 0.15 + 0.15 + 0.15; +//! # let b: f32 = 0.1 + 0.1 + 0.25; +//! assert!( approx_eq!(f32, a, b, ulps = 2) ); +//! assert!( approx_eq!(f32, a, b, epsilon = 0.00000003) ); +//! assert!( approx_eq!(f32, a, b, epsilon = 0.00000003, ulps = 2) ); +//! assert!( approx_eq!(f32, a, b, (0.0, 2)) ); +//! assert!( approx_eq!(f32, a, b, F32Margin { epsilon: 0.0, ulps: 2 }) ); +//! assert!( approx_eq!(f32, a, b, F32Margin::default()) ); +//! assert!( approx_eq!(f32, a, b) ); // uses the default +//! # } +//! ``` +//! +//! For most cases, I recommend you use a smallish integer for the `ulps` parameter (1 to 5 +//! or so), and a similar small multiple of the floating point's EPSILON constant (1.0 to 5.0 +//! or so), but there are *plenty* of cases where this is insufficient. +//! +//! ## Implementing these traits +//! +//! You can implement `ApproxEq` for your own complex types like shown below. +//! The floating point type `F` must be `Copy`, but for large types you can implement +//! it for references to your type as shown. +//! +//! ``` +//! use float_cmp::ApproxEq; +//! +//! pub struct Vec2<F> { +//! pub x: F, +//! pub y: F, +//! } +//! +//! impl<'a, M: Copy + Default, F: Copy + ApproxEq<Margin=M>> ApproxEq for &'a Vec2<F> { +//! type Margin = M; +//! +//! fn approx_eq<T: Into<Self::Margin>>(self, other: Self, margin: T) -> bool { +//! let margin = margin.into(); +//! self.x.approx_eq(other.x, margin) +//! && self.y.approx_eq(other.y, margin) +//! } +//! } +//! ``` +//! +//! ## Non floating-point types +//! +//! `ApproxEq` can be implemented for non floating-point types as well, since `Margin` is +//! an associated type. +//! +//! The `efloat` crate implements (or soon will implement) `ApproxEq` for a compound type +//! that tracks floating point error bounds by checking if the error bounds overlap. +//! In that case `type Margin = ()`. +//! +//! ## Inspiration +//! +//! This crate was inspired by this Random ASCII blog post: +//! +//! [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/) + +#[cfg(feature="num-traits")] +extern crate num_traits; + +#[macro_use] +mod macros; + +pub fn trials() { + println!("are they approximately equal?: {:?}", + approx_eq!(f32, 1.0, 1.0000001)); +} + +mod ulps; +pub use self::ulps::Ulps; + +mod ulps_eq; +pub use self::ulps_eq::ApproxEqUlps; + +mod eq; +pub use self::eq::{ApproxEq, F32Margin, F64Margin}; + +#[cfg(feature="num-traits")] +mod ratio; +#[cfg(feature="num-traits")] +pub use self::ratio::ApproxEqRatio; diff --git a/third_party/rust/float-cmp/src/macros.rs b/third_party/rust/float-cmp/src/macros.rs new file mode 100644 index 0000000000..7eeaa30fd9 --- /dev/null +++ b/third_party/rust/float-cmp/src/macros.rs @@ -0,0 +1,77 @@ + +#[macro_export] +macro_rules! approx_eq { + ($typ:ty, $lhs:expr, $rhs:expr) => { + { + let m: <$typ as $crate::ApproxEq>::Margin = Default::default(); + <$typ as $crate::ApproxEq>::approx_eq($lhs, $rhs, m) + } + }; + ($typ:ty, $lhs:expr, $rhs:expr $(, $set:ident = $val:expr)*) => { + { + let m = <$typ as $crate::ApproxEq>::Margin::zero()$(.$set($val))*; + <$typ as $crate::ApproxEq>::approx_eq($lhs, $rhs, m) + } + }; + ($typ:ty, $lhs:expr, $rhs:expr, $marg:expr) => { + { + <$typ as $crate::ApproxEq>::approx_eq($lhs, $rhs, $marg) + } + }; +} + +// Until saturating_abs() comes out of nightly, we have to code it ourselves. +macro_rules! saturating_abs_i32 { + ($val:expr) => { + if $val.is_negative() { + match $val.checked_neg() { + Some(v) => v, + None => std::i32::MAX + } + } else { + $val + } + }; +} +macro_rules! saturating_abs_i64 { + ($val:expr) => { + if $val.is_negative() { + match $val.checked_neg() { + Some(v) => v, + None => std::i64::MAX + } + } else { + $val + } + }; +} + +#[test] +fn test_macro() { + let a: f32 = 0.15 + 0.15 + 0.15; + let b: f32 = 0.1 + 0.1 + 0.25; + assert!( approx_eq!(f32, a, b) ); // uses the default + assert!( approx_eq!(f32, a, b, ulps = 2) ); + assert!( approx_eq!(f32, a, b, epsilon = 0.00000003) ); + assert!( approx_eq!(f32, a, b, epsilon = 0.00000003, ulps = 2) ); + assert!( approx_eq!(f32, a, b, (0.0, 2)) ); +} + +#[test] +fn test_macro_2() { + assert!( approx_eq!(f64, 1000000_f64, 1000000.0000000003_f64) ); + assert!( approx_eq!(f64, 1000000_f64, 1000000.0000000003_f64, ulps=3) ); + assert!( approx_eq!(f64, 1000000_f64, 1000000.0000000003_f64, epsilon=0.0000000004) ); + assert!( approx_eq!(f64, 1000000_f64, 1000000.0000000003_f64, (0.0000000004, 0)) ); + assert!( approx_eq!(f64, 1000000_f64, 1000000.0000000003_f64, (0.0, 3)) ); +} + +#[test] +fn test_macro_3() { + use crate::F32Margin; + + let a: f32 = 0.15 + 0.15 + 0.15; + let b: f32 = 0.1 + 0.1 + 0.25; + assert!( approx_eq!(f32, a, b, F32Margin { epsilon: 0.0, ulps: 2 }) ); + assert!( approx_eq!(f32, a, b, F32Margin::default()) ); +} diff --git a/third_party/rust/float-cmp/src/ratio.rs b/third_party/rust/float-cmp/src/ratio.rs new file mode 100644 index 0000000000..0a8654bba8 --- /dev/null +++ b/third_party/rust/float-cmp/src/ratio.rs @@ -0,0 +1,142 @@ +// Copyright 2014-2018 Optimal Computing (NZ) Ltd. +// Licensed under the MIT license. See LICENSE for details. + +use std::cmp::PartialOrd; +use std::ops::{Sub,Div,Neg}; +use num_traits::Zero; + +/// ApproxEqRatio is a trait for approximate equality comparisons bounding the ratio +/// of the difference to the larger. +pub trait ApproxEqRatio : Div<Output = Self> + Sub<Output = Self> + Neg<Output = Self> + + PartialOrd + Zero + Sized + Copy +{ + /// This method tests if `self` and `other` are nearly equal by bounding the + /// difference between them to some number much less than the larger of the two. + /// This bound is set as the ratio of the difference to the larger. + fn approx_eq_ratio(&self, other: &Self, ratio: Self) -> bool { + + // Not equal if signs are not equal + if *self < Self::zero() && *other > Self::zero() { return false; } + if *self > Self::zero() && *other < Self::zero() { return false; } + + // Handle all zero cases + match (*self == Self::zero(), *other == Self::zero()) { + (true,true) => return true, + (true,false) => return false, + (false,true) => return false, + _ => { } + } + + // abs + let (s,o) = if *self < Self::zero() { + (-*self, -*other) + } else { + (*self, *other) + }; + + let (smaller,larger) = if s < o { + (s,o) + } else { + (o,s) + }; + let difference: Self = larger.sub(smaller); + let actual_ratio: Self = difference.div(larger); + actual_ratio < ratio + } + + /// This method tests if `self` and `other` are not nearly equal by bounding the + /// difference between them to some number much less than the larger of the two. + /// This bound is set as the ratio of the difference to the larger. + #[inline] + fn approx_ne_ratio(&self, other: &Self, ratio: Self) -> bool { + !self.approx_eq_ratio(other, ratio) + } +} + +impl ApproxEqRatio for f32 { } + +#[test] +fn f32_approx_eq_ratio_test1() { + let x: f32 = 0.00004_f32; + let y: f32 = 0.00004001_f32; + assert!(x.approx_eq_ratio(&y, 0.00025)); + assert!(y.approx_eq_ratio(&x, 0.00025)); + assert!(x.approx_ne_ratio(&y, 0.00024)); + assert!(y.approx_ne_ratio(&x, 0.00024)); +} + +#[test] +fn f32_approx_eq_ratio_test2() { + let x: f32 = 0.00000000001_f32; + let y: f32 = 0.00000000005_f32; + assert!(x.approx_eq_ratio(&y, 0.81)); + assert!(y.approx_ne_ratio(&x, 0.79)); +} + +#[test] +fn f32_approx_eq_ratio_test_zero_eq_zero_returns_true() { + let x: f32 = 0.0_f32; + assert!(x.approx_eq_ratio(&x,0.1) == true); +} + +#[test] +fn f32_approx_eq_ratio_test_zero_ne_zero_returns_false() { + let x: f32 = 0.0_f32; + assert!(x.approx_ne_ratio(&x,0.1) == false); +} + +#[test] +fn f32_approx_eq_ratio_test_against_a_zero_is_false() { + let x: f32 = 0.0_f32; + let y: f32 = 0.1_f32; + assert!(x.approx_eq_ratio(&y,0.1) == false); + assert!(y.approx_eq_ratio(&x,0.1) == false); +} + +#[test] +fn f32_approx_eq_ratio_test_negative_numbers() { + let x: f32 = -3.0_f32; + let y: f32 = -4.0_f32; + // -3 and -4 should not be equal at a ratio of 0.1 + assert!(x.approx_eq_ratio(&y,0.1) == false); +} + +impl ApproxEqRatio for f64 { } + +#[test] +fn f64_approx_eq_ratio_test1() { + let x: f64 = 0.000000004_f64; + let y: f64 = 0.000000004001_f64; + assert!(x.approx_eq_ratio(&y, 0.00025)); + assert!(y.approx_eq_ratio(&x, 0.00025)); + assert!(x.approx_ne_ratio(&y, 0.00024)); + assert!(y.approx_ne_ratio(&x, 0.00024)); +} + +#[test] +fn f64_approx_eq_ratio_test2() { + let x: f64 = 0.0000000000000001_f64; + let y: f64 = 0.0000000000000005_f64; + assert!(x.approx_eq_ratio(&y, 0.81)); + assert!(y.approx_ne_ratio(&x, 0.79)); +} + +#[test] +fn f64_approx_eq_ratio_test_zero_eq_zero_returns_true() { + let x: f64 = 0.0_f64; + assert!(x.approx_eq_ratio(&x,0.1) == true); +} + +#[test] +fn f64_approx_eq_ratio_test_zero_ne_zero_returns_false() { + let x: f64 = 0.0_f64; + assert!(x.approx_ne_ratio(&x,0.1) == false); +} + +#[test] +fn f64_approx_eq_ratio_test_negative_numbers() { + let x: f64 = -3.0_f64; + let y: f64 = -4.0_f64; + // -3 and -4 should not be equal at a ratio of 0.1 + assert!(x.approx_eq_ratio(&y,0.1) == false); +} diff --git a/third_party/rust/float-cmp/src/ulps.rs b/third_party/rust/float-cmp/src/ulps.rs new file mode 100644 index 0000000000..51f186f94e --- /dev/null +++ b/third_party/rust/float-cmp/src/ulps.rs @@ -0,0 +1,240 @@ +// Copyright 2014-2018 Optimal Computing (NZ) Ltd. +// Licensed under the MIT license. See LICENSE for details. + +#[cfg(feature="num_traits")] +use num_traits::NumCast; + +/// A trait for floating point numbers which computes the number of representable +/// values or ULPs (Units of Least Precision) that separate the two given values. +#[cfg(feature="num_traits")] +pub trait Ulps { + type U: Copy + NumCast; + + /// The number of representable values or ULPs (Units of Least Precision) that + /// separate `self` and `other`. The result `U` is an integral value, and will + /// be zero if `self` and `other` are exactly equal. + fn ulps(&self, other: &Self) -> <Self as Ulps>::U; + + /// The next representable number above this one + fn next(&self) -> Self; + + /// The previous representable number below this one + fn prev(&self) -> Self; +} + +#[cfg(not(feature="num_traits"))] +pub trait Ulps { + type U: Copy; + + /// The number of representable values or ULPs (Units of Least Precision) that + /// separate `self` and `other`. The result `U` is an integral value, and will + /// be zero if `self` and `other` are exactly equal. + fn ulps(&self, other: &Self) -> <Self as Ulps>::U; + + /// The next representable number above this one + fn next(&self) -> Self; + + /// The previous representable number below this one + fn prev(&self) -> Self; +} + +impl Ulps for f32 { + type U = i32; + + fn ulps(&self, other: &f32) -> i32 { + + // IEEE754 defined floating point storage representation to + // maintain their order when their bit patterns are interpreted as + // integers. This is a huge boon to the task at hand, as we can + // reinterpret them as integers to find out how many ULPs apart any + // two floats are + + // Setup integer representations of the input + let ai32: i32 = self.to_bits() as i32; + let bi32: i32 = other.to_bits() as i32; + + ai32.wrapping_sub(bi32) + } + + fn next(&self) -> Self { + if self.is_infinite() && *self > 0.0 { + *self + } else if *self == -0.0 && self.is_sign_negative() { + 0.0 + } else { + let mut u = self.to_bits(); + if *self >= 0.0 { + u += 1; + } else { + u -= 1; + } + f32::from_bits(u) + } + } + + fn prev(&self) -> Self { + if self.is_infinite() && *self < 0.0 { + *self + } else if *self == 0.0 && self.is_sign_positive() { + -0.0 + } else { + let mut u = self.to_bits(); + if *self <= -0.0 { + u += 1; + } else { + u -= 1; + } + f32::from_bits(u) + } + } +} + +#[test] +fn f32_ulps_test1() { + let x: f32 = 1000000_f32; + let y: f32 = 1000000.1_f32; + println!("DIST IS {}",x.ulps(&y)); + assert!(x.ulps(&y) == -2); +} + +#[test] +fn f32_ulps_test2() { + let pzero: f32 = f32::from_bits(0x00000000_u32); + let nzero: f32 = f32::from_bits(0x80000000_u32); + println!("DIST IS {}",pzero.ulps(&nzero)); + assert!(pzero.ulps(&nzero) == -2147483648); +} +#[test] +fn f32_ulps_test3() { + let pinf: f32 = f32::from_bits(0x7f800000_u32); + let ninf: f32 = f32::from_bits(0xff800000_u32); + println!("DIST IS {}",pinf.ulps(&ninf)); + assert!(pinf.ulps(&ninf) == -2147483648); +} + +#[test] +fn f32_ulps_test4() { + let x: f32 = f32::from_bits(0x63a7f026_u32); + let y: f32 = f32::from_bits(0x63a7f023_u32); + println!("DIST IS {}",x.ulps(&y)); + assert!(x.ulps(&y) == 3); +} + +#[test] +fn f32_ulps_test5() { + let x: f32 = 2.0; + let ulps: i32 = x.to_bits() as i32; + let x2: f32 = <f32>::from_bits(ulps as u32); + assert_eq!(x, x2); +} + +#[test] +fn f32_ulps_test6() { + let negzero: f32 = -0.; + let zero: f32 = 0.; + assert_eq!(negzero.next(), zero); + assert_eq!(zero.prev(), negzero); + assert!(negzero.prev() < 0.0); + assert!(zero.next() > 0.0); +} + +impl Ulps for f64 { + type U = i64; + + fn ulps(&self, other: &f64) -> i64 { + + // IEEE754 defined floating point storage representation to + // maintain their order when their bit patterns are interpreted as + // integers. This is a huge boon to the task at hand, as we can + // reinterpret them as integers to find out how many ULPs apart any + // two floats are + + // Setup integer representations of the input + let ai64: i64 = self.to_bits() as i64; + let bi64: i64 = other.to_bits() as i64; + + ai64.wrapping_sub(bi64) + } + + fn next(&self) -> Self { + if self.is_infinite() && *self > 0.0 { + *self + } else if *self == -0.0 && self.is_sign_negative() { + 0.0 + } else { + let mut u = self.to_bits(); + if *self >= 0.0 { + u += 1; + } else { + u -= 1; + } + f64::from_bits(u) + } + } + + fn prev(&self) -> Self { + if self.is_infinite() && *self < 0.0 { + *self + } else if *self == 0.0 && self.is_sign_positive() { + -0.0 + } else { + let mut u = self.to_bits(); + if *self <= -0.0 { + u += 1; + } else { + u -= 1; + } + f64::from_bits(u) + } + } +} + +#[test] +fn f64_ulps_test1() { + let x: f64 = 1000000_f64; + let y: f64 = 1000000.00000001_f64; + println!("DIST IS {}",x.ulps(&y)); + assert!(x.ulps(&y) == -86); +} + +#[test] +fn f64_ulps_test2() { + let pzero: f64 = f64::from_bits(0x0000000000000000_u64); + let nzero: f64 = f64::from_bits(0x8000000000000000_u64); + println!("DIST IS {}",pzero.ulps(&nzero)); + assert!(pzero.ulps(&nzero) == -9223372036854775808i64); +} +#[test] +fn f64_ulps_test3() { + let pinf: f64 = f64::from_bits(0x7f80000000000000_u64); + let ninf: f64 = f64::from_bits(0xff80000000000000_u64); + println!("DIST IS {}",pinf.ulps(&ninf)); + assert!(pinf.ulps(&ninf) == -9223372036854775808i64); +} + +#[test] +fn f64_ulps_test4() { + let x: f64 = f64::from_bits(0xd017f6cc63a7f026_u64); + let y: f64 = f64::from_bits(0xd017f6cc63a7f023_u64); + println!("DIST IS {}",x.ulps(&y)); + assert!(x.ulps(&y) == 3); +} + +#[test] +fn f64_ulps_test5() { + let x: f64 = 2.0; + let ulps: i64 = x.to_bits() as i64; + let x2: f64 = <f64>::from_bits(ulps as u64); + assert_eq!(x, x2); +} + +#[test] +fn f64_ulps_test6() { + let negzero: f64 = -0.; + let zero: f64 = 0.; + assert_eq!(negzero.next(), zero); + assert_eq!(zero.prev(), negzero); + assert!(negzero.prev() < 0.0); + assert!(zero.next() > 0.0); +} + diff --git a/third_party/rust/float-cmp/src/ulps_eq.rs b/third_party/rust/float-cmp/src/ulps_eq.rs new file mode 100644 index 0000000000..9dc0c37f40 --- /dev/null +++ b/third_party/rust/float-cmp/src/ulps_eq.rs @@ -0,0 +1,119 @@ +// Copyright 2014-2018 Optimal Computing (NZ) Ltd. +// Licensed under the MIT license. See LICENSE for details. + +use super::Ulps; + +/// ApproxEqUlps is a trait for approximate equality comparisons. +/// The associated type Flt is a floating point type which implements Ulps, and is +/// required so that this trait can be implemented for compound types (e.g. vectors), +/// not just for the floats themselves. +pub trait ApproxEqUlps { + type Flt: Ulps; + + /// This method tests for `self` and `other` values to be approximately equal + /// within ULPs (Units of Least Precision) floating point representations. + /// Differing signs are always unequal with this method, and zeroes are only + /// equal to zeroes. Use approx_eq() from the ApproxEq trait if that is more + /// appropriate. + fn approx_eq_ulps(&self, other: &Self, ulps: <Self::Flt as Ulps>::U) -> bool; + + /// This method tests for `self` and `other` values to be not approximately + /// equal within ULPs (Units of Least Precision) floating point representations. + /// Differing signs are always unequal with this method, and zeroes are only + /// equal to zeroes. Use approx_eq() from the ApproxEq trait if that is more + /// appropriate. + #[inline] + fn approx_ne_ulps(&self, other: &Self, ulps: <Self::Flt as Ulps>::U) -> bool { + !self.approx_eq_ulps(other, ulps) + } +} + +impl ApproxEqUlps for f32 { + type Flt = f32; + + fn approx_eq_ulps(&self, other: &f32, ulps: i32) -> bool { + // -0 and +0 are drastically far in ulps terms, so + // we need a special case for that. + if *self==*other { return true; } + + // Handle differing signs as a special case, even if + // they are very close, most people consider them + // unequal. + if self.is_sign_positive() != other.is_sign_positive() { return false; } + + let diff: i32 = self.ulps(other); + diff >= -ulps && diff <= ulps + } +} + +#[test] +fn f32_approx_eq_ulps_test1() { + let f: f32 = 0.1_f32; + let mut sum: f32 = 0.0_f32; + for _ in 0_isize..10_isize { sum += f; } + let product: f32 = f * 10.0_f32; + assert!(sum != product); // Should not be directly equal: + println!("Ulps Difference: {}",sum.ulps(&product)); + assert!(sum.approx_eq_ulps(&product,1) == true); // But should be close + assert!(sum.approx_eq_ulps(&product,0) == false); +} +#[test] +fn f32_approx_eq_ulps_test2() { + let x: f32 = 1000000_f32; + let y: f32 = 1000000.1_f32; + assert!(x != y); // Should not be directly equal + println!("Ulps Difference: {}",x.ulps(&y)); + assert!(x.approx_eq_ulps(&y,2) == true); + assert!(x.approx_eq_ulps(&y,1) == false); +} +#[test] +fn f32_approx_eq_ulps_test_zeroes() { + let x: f32 = 0.0_f32; + let y: f32 = -0.0_f32; + assert!(x.approx_eq_ulps(&y,0) == true); +} + +impl ApproxEqUlps for f64 { + type Flt = f64; + + fn approx_eq_ulps(&self, other: &f64, ulps: i64) -> bool { + // -0 and +0 are drastically far in ulps terms, so + // we need a special case for that. + if *self==*other { return true; } + + // Handle differing signs as a special case, even if + // they are very close, most people consider them + // unequal. + if self.is_sign_positive() != other.is_sign_positive() { return false; } + + let diff: i64 = self.ulps(other); + diff >= -ulps && diff <= ulps + } +} + +#[test] +fn f64_approx_eq_ulps_test1() { + let f: f64 = 0.1_f64; + let mut sum: f64 = 0.0_f64; + for _ in 0_isize..10_isize { sum += f; } + let product: f64 = f * 10.0_f64; + assert!(sum != product); // Should not be directly equal: + println!("Ulps Difference: {}",sum.ulps(&product)); + assert!(sum.approx_eq_ulps(&product,1) == true); // But should be close + assert!(sum.approx_eq_ulps(&product,0) == false); +} +#[test] +fn f64_approx_eq_ulps_test2() { + let x: f64 = 1000000_f64; + let y: f64 = 1000000.0000000003_f64; + assert!(x != y); // Should not be directly equal + println!("Ulps Difference: {}",x.ulps(&y)); + assert!(x.approx_eq_ulps(&y,3) == true); + assert!(x.approx_eq_ulps(&y,2) == false); +} +#[test] +fn f64_approx_eq_ulps_test_zeroes() { + let x: f64 = 0.0_f64; + let y: f64 = -0.0_f64; + assert!(x.approx_eq_ulps(&y,0) == true); +} |