Bug 948984 - Add functions to fuzzily compare float numbers. r=bjacob, r=Waldo
authorKartikaya Gupta <kgupta@mozilla.com>
Wed, 05 Feb 2014 17:04:42 -0500
changeset 167107 93e0be61f0682a1c19d16669325f3d03d288168b
parent 167106 fb4ffbea406d405f7a76febc9e78572675cbae7a
child 167108 285204b60e94f5bdadd2c9b86213cc41efab3b54
push id26159
push usercbook@mozilla.com
push dateThu, 06 Feb 2014 11:50:11 +0000
treeherdermozilla-central@b04e2524e2eb [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbjacob, Waldo
bugs948984
milestone30.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 948984 - Add functions to fuzzily compare float numbers. r=bjacob, r=Waldo
mfbt/FloatingPoint.h
mfbt/tests/TestFloatingPoint.cpp
--- a/mfbt/FloatingPoint.h
+++ b/mfbt/FloatingPoint.h
@@ -7,16 +7,17 @@
 /* Various predicates and operations on IEEE-754 floating point types. */
 
 #ifndef mozilla_FloatingPoint_h
 #define mozilla_FloatingPoint_h
 
 #include "mozilla/Assertions.h"
 #include "mozilla/Attributes.h"
 #include "mozilla/Casting.h"
+#include "mozilla/MathAlgorithms.h"
 #include "mozilla/Types.h"
 
 #include <stdint.h>
 
 namespace mozilla {
 
 /*
  * It's reasonable to ask why we have this header at all.  Don't isnan,
@@ -285,16 +286,80 @@ SpecificFloatNaN(int signbit, uint32_t s
 
   float f = BitwiseCast<float>((signbit ? FloatSignBit : 0) |
                                  FloatExponentBits |
                                  significand);
   MOZ_ASSERT(IsFloatNaN(f));
   return f;
 }
 
+namespace detail {
+
+template<typename T>
+struct FuzzyEqualsEpsilon;
+
+template<>
+struct FuzzyEqualsEpsilon<float>
+{
+  // A number near 1e-5 that is exactly representable in
+  // floating point
+  static const float value() { return 1.0f / (1 << 17); }
+};
+
+template<>
+struct FuzzyEqualsEpsilon<double>
+{
+  // A number near 1e-12 that is exactly representable in
+  // a double
+  static const double value() { return 1.0 / (1LL << 40); }
+};
+
+} // namespace detail
+
+/**
+ * Compare two floating point values for equality, modulo rounding error. That
+ * is, the two values are considered equal if they are both not NaN and if they
+ * are less than or equal to epsilon apart. The default value of epsilon is near
+ * 1e-5.
+ *
+ * For most scenarios you will want to use FuzzyEqualsMultiplicative instead,
+ * as it is more reasonable over the entire range of floating point numbers.
+ * This additive version should only be used if you know the range of the numbers
+ * you are dealing with is bounded and stays around the same order of magnitude.
+ */
+template<typename T>
+static MOZ_ALWAYS_INLINE bool
+FuzzyEqualsAdditive(T val1, T val2, T epsilon = detail::FuzzyEqualsEpsilon<T>::value())
+{
+  static_assert(IsFloatingPoint<T>::value, "floating point type required");
+  return Abs(val1 - val2) <= epsilon;
+}
+
+/**
+ * Compare two floating point values for equality, allowing for rounding error
+ * relative to the magnitude of the values. That is, the two values are
+ * considered equal if they are both not NaN and they are less than or equal to
+ * some epsilon apart, where the epsilon is scaled by the smaller of the two
+ * argument values.
+ *
+ * In most cases you will want to use this rather than FuzzyEqualsAdditive, as
+ * this function effectively masks out differences in the bottom few bits of
+ * the floating point numbers being compared, regardless of what order of magnitude
+ * those numbers are at.
+ */
+template<typename T>
+static MOZ_ALWAYS_INLINE bool
+FuzzyEqualsMultiplicative(T val1, T val2, T epsilon = detail::FuzzyEqualsEpsilon<T>::value())
+{
+  static_assert(IsFloatingPoint<T>::value, "floating point type required");
+  // can't use std::min because of bug 965340
+  T smaller = Abs(val1) < Abs(val2) ? Abs(val1) : Abs(val2);
+  return Abs(val1 - val2) <= epsilon * smaller;
+}
+
 /**
  * Returns true if the given value can be losslessly represented as an IEEE-754
  * single format number, false otherwise.  All NaN values are considered
  * representable (notwithstanding that the exact bit pattern of a double format
  * NaN value can't be exactly represented in single format).
  *
  * This function isn't inlined to avoid buggy optimizations by MSVC.
  */
--- a/mfbt/tests/TestFloatingPoint.cpp
+++ b/mfbt/tests/TestFloatingPoint.cpp
@@ -7,23 +7,26 @@
 
 #include <math.h>
 
 using mozilla::DoublesAreIdentical;
 using mozilla::DoubleExponentBias;
 using mozilla::DoubleEqualsInt32;
 using mozilla::DoubleIsInt32;
 using mozilla::ExponentComponent;
+using mozilla::FuzzyEqualsAdditive;
+using mozilla::FuzzyEqualsMultiplicative;
 using mozilla::IsFinite;
 using mozilla::IsInfinite;
 using mozilla::IsNaN;
 using mozilla::IsNegative;
 using mozilla::IsNegativeZero;
 using mozilla::NegativeInfinity;
 using mozilla::PositiveInfinity;
+using mozilla::SpecificFloatNaN;
 using mozilla::SpecificNaN;
 using mozilla::UnspecifiedNaN;
 
 static void
 ShouldBeIdentical(double d1, double d2)
 {
   MOZ_ASSERT(DoublesAreIdentical(d1, d2));
   MOZ_ASSERT(DoublesAreIdentical(d2, d1));
@@ -185,15 +188,161 @@ TestPredicates()
   MOZ_ASSERT(!DoubleEqualsInt32(0.5, &i));
   MOZ_ASSERT(!DoubleEqualsInt32(double(INT32_MAX) + 0.1, &i));
   MOZ_ASSERT(!DoubleEqualsInt32(double(INT32_MIN) - 0.1, &i));
   MOZ_ASSERT(!DoubleEqualsInt32(NegativeInfinity(), &i));
   MOZ_ASSERT(!DoubleEqualsInt32(PositiveInfinity(), &i));
   MOZ_ASSERT(!DoubleEqualsInt32(UnspecifiedNaN(), &i));
 }
 
+static void
+TestFloatsAreApproximatelyEqual()
+{
+  float epsilon = mozilla::detail::FuzzyEqualsEpsilon<float>::value();
+  float lessThanEpsilon = epsilon / 2.0f;
+  float moreThanEpsilon = epsilon * 2.0f;
+
+  // Additive tests using the default epsilon
+  // ... around 1.0
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0f, 1.0f + lessThanEpsilon));
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0f, 1.0f - lessThanEpsilon));
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0f, 1.0f + epsilon));
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0f, 1.0f - epsilon));
+  MOZ_ASSERT(!FuzzyEqualsAdditive(1.0f, 1.0f + moreThanEpsilon));
+  MOZ_ASSERT(!FuzzyEqualsAdditive(1.0f, 1.0f - moreThanEpsilon));
+  // ... around 1.0e2 (this is near the upper bound of the range where
+  // adding moreThanEpsilon will still be representable and return false)
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0e2f, 1.0e2f + lessThanEpsilon));
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0e2f, 1.0e2f + epsilon));
+  MOZ_ASSERT(!FuzzyEqualsAdditive(1.0e2f, 1.0e2f + moreThanEpsilon));
+  // ... around 1.0e-10
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0e-10f, 1.0e-10f + lessThanEpsilon));
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0e-10f, 1.0e-10f + epsilon));
+  MOZ_ASSERT(!FuzzyEqualsAdditive(1.0e-10f, 1.0e-10f + moreThanEpsilon));
+  // ... straddling 0
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0e-6f, -1.0e-6f));
+  MOZ_ASSERT(!FuzzyEqualsAdditive(1.0e-5f, -1.0e-5f));
+  // Using a small epsilon
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0e-5f, 1.0e-5f + 1.0e-10f, 1.0e-9f));
+  MOZ_ASSERT(!FuzzyEqualsAdditive(1.0e-5f, 1.0e-5f + 1.0e-10f, 1.0e-11f));
+  // Using a big epsilon
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0e20f, 1.0e20f + 1.0e15f, 1.0e16f));
+  MOZ_ASSERT(!FuzzyEqualsAdditive(1.0e20f, 1.0e20f + 1.0e15f, 1.0e14f));
+
+  // Multiplicative tests using the default epsilon
+  // ... around 1.0
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(1.0f, 1.0f + lessThanEpsilon));
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(1.0f, 1.0f - lessThanEpsilon));
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(1.0f, 1.0f + epsilon));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(1.0f, 1.0f - epsilon));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(1.0f, 1.0f + moreThanEpsilon));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(1.0f, 1.0f - moreThanEpsilon));
+  // ... around 1.0e10
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(1.0e10f, 1.0e10f + (lessThanEpsilon * 1.0e10f)));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(1.0e10f, 1.0e10f + (moreThanEpsilon * 1.0e10f)));
+  // ... around 1.0e-10
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(1.0e-10f, 1.0e-10f + (lessThanEpsilon * 1.0e-10f)));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(1.0e-10f, 1.0e-10f + (moreThanEpsilon * 1.0e-10f)));
+  // ... straddling 0
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(1.0e-6f, -1.0e-6f));
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(1.0e-6f, -1.0e-6f, 1.0e2f));
+  // Using a small epsilon
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(1.0e-5f, 1.0e-5f + 1.0e-10f, 1.0e-4f));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(1.0e-5f, 1.0e-5f + 1.0e-10f, 1.0e-5f));
+  // Using a big epsilon
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(1.0f, 2.0f, 1.0f));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(1.0f, 2.0f, 0.1f));
+
+  // "real world case"
+  float oneThird = 10.0f / 3.0f;
+  MOZ_ASSERT(FuzzyEqualsAdditive(10.0f, 3.0f * oneThird));
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(10.0f, 3.0f * oneThird));
+  // NaN check
+  MOZ_ASSERT(!FuzzyEqualsAdditive(SpecificFloatNaN(1, 1), SpecificFloatNaN(1, 1)));
+  MOZ_ASSERT(!FuzzyEqualsAdditive(SpecificFloatNaN(1, 2), SpecificFloatNaN(0, 8)));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(SpecificFloatNaN(1, 1), SpecificFloatNaN(1, 1)));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(SpecificFloatNaN(1, 2), SpecificFloatNaN(0, 200)));
+}
+
+static void
+TestDoublesAreApproximatelyEqual()
+{
+  double epsilon = mozilla::detail::FuzzyEqualsEpsilon<double>::value();
+  double lessThanEpsilon = epsilon / 2.0;
+  double moreThanEpsilon = epsilon * 2.0;
+
+  // Additive tests using the default epsilon
+  // ... around 1.0
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0, 1.0 + lessThanEpsilon));
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0, 1.0 - lessThanEpsilon));
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0, 1.0 + epsilon));
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0, 1.0 - epsilon));
+  MOZ_ASSERT(!FuzzyEqualsAdditive(1.0, 1.0 + moreThanEpsilon));
+  MOZ_ASSERT(!FuzzyEqualsAdditive(1.0, 1.0 - moreThanEpsilon));
+  // ... around 1.0e4 (this is near the upper bound of the range where
+  // adding moreThanEpsilon will still be representable and return false)
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0e4, 1.0e4 + lessThanEpsilon));
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0e4, 1.0e4 + epsilon));
+  MOZ_ASSERT(!FuzzyEqualsAdditive(1.0e4, 1.0e4 + moreThanEpsilon));
+  // ... around 1.0e-25
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0e-25, 1.0e-25 + lessThanEpsilon));
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0e-25, 1.0e-25 + epsilon));
+  MOZ_ASSERT(!FuzzyEqualsAdditive(1.0e-25, 1.0e-25 + moreThanEpsilon));
+  // ... straddling 0
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0e-13, -1.0e-13));
+  MOZ_ASSERT(!FuzzyEqualsAdditive(1.0e-12, -1.0e-12));
+  // Using a small epsilon
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0e-15, 1.0e-15 + 1.0e-30, 1.0e-29));
+  MOZ_ASSERT(!FuzzyEqualsAdditive(1.0e-15, 1.0e-15 + 1.0e-30, 1.0e-31));
+  // Using a big epsilon
+  MOZ_ASSERT(FuzzyEqualsAdditive(1.0e40, 1.0e40 + 1.0e25, 1.0e26));
+  MOZ_ASSERT(!FuzzyEqualsAdditive(1.0e40, 1.0e40 + 1.0e25, 1.0e24));
+
+  // Multiplicative tests using the default epsilon
+  // ... around 1.0
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(1.0, 1.0 + lessThanEpsilon));
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(1.0, 1.0 - lessThanEpsilon));
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(1.0, 1.0 + epsilon));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(1.0, 1.0 - epsilon));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(1.0, 1.0 + moreThanEpsilon));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(1.0, 1.0 - moreThanEpsilon));
+  // ... around 1.0e30
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(1.0e30, 1.0e30 + (lessThanEpsilon * 1.0e30)));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(1.0e30, 1.0e30 + (moreThanEpsilon * 1.0e30)));
+  // ... around 1.0e-30
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(1.0e-30, 1.0e-30 + (lessThanEpsilon * 1.0e-30)));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(1.0e-30, 1.0e-30 + (moreThanEpsilon * 1.0e-30)));
+  // ... straddling 0
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(1.0e-6, -1.0e-6));
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(1.0e-6, -1.0e-6, 1.0e2));
+  // Using a small epsilon
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(1.0e-15, 1.0e-15 + 1.0e-30, 1.0e-15));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(1.0e-15, 1.0e-15 + 1.0e-30, 1.0e-16));
+  // Using a big epsilon
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(1.0e40, 2.0e40, 1.0));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(1.0e40, 2.0e40, 0.1));
+
+  // "real world case"
+  double oneThird = 10.0 / 3.0;
+  MOZ_ASSERT(FuzzyEqualsAdditive(10.0, 3.0 * oneThird));
+  MOZ_ASSERT(FuzzyEqualsMultiplicative(10.0, 3.0 * oneThird));
+  // NaN check
+  MOZ_ASSERT(!FuzzyEqualsAdditive(SpecificNaN(1, 1), SpecificNaN(1, 1)));
+  MOZ_ASSERT(!FuzzyEqualsAdditive(SpecificNaN(1, 2), SpecificNaN(0, 8)));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(SpecificNaN(1, 1), SpecificNaN(1, 1)));
+  MOZ_ASSERT(!FuzzyEqualsMultiplicative(SpecificNaN(1, 2), SpecificNaN(0, 200)));
+}
+
+static void
+TestAreApproximatelyEqual()
+{
+  TestFloatsAreApproximatelyEqual();
+  TestDoublesAreApproximatelyEqual();
+}
+
 int
 main()
 {
   TestDoublesAreIdentical();
   TestExponentComponent();
   TestPredicates();
+  TestAreApproximatelyEqual();
 }