Floating-point comparison for mortals

[ElusiveTau]

I see a menacing dark cloud looming on the horizon and I wonder why other beginners aren't as concerned as I am.
Have they ever had to deal with floating point comparisons?
Does it not bother them that some mathematical inequalities, completely reasonable for real numbers, seem to unexplicably fail?
Maybe real-world problems are simple enough that "abs(a-b) < epsilon" suffice?

I recently read this [1] article and fell into despair about how difficult it is to compare floating point numbers. I took a shot at reading one of the white papers alluded to in the article, [2], on "Fortune-van-Wyk bound", and found it really dense (I haven't finished reading).

The problem surely can't be trivial (if someone went through the trouble of writing 59 pages about it) but where rubber meets the road, *someone* had to use some non-trivial version of these algorithms to deal with floating-point applications. I can't imagine that we always work in integer-land, especially if the application is naturally graphical (e.g., google sketchup).

So I ask: where is the happy medium between "abs(a-b) < epsilon" and [2]?

[1] double - and how to use it
https://cplusplus.com/forum/articles/3827/

[2] Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates
https://people.eecs.berkeley.edu/~jrs/papers/robustr.pdf

[kigar64551]

bool qFuzzyCompare(double p1, double p2)
Compares the floating point value p1 and p2 and returns true if they are considered equal, otherwise false.

template <typename T>
constexpr inline const T &qMin(const T &a, const T &b) { return (a < b) ? a : b; }

static inline bool qFuzzyCompare(double p1, double p2)
{
    return (qAbs(p1 - p2) * 1000000000000. <= qMin(qAbs(p1), qAbs(p2)));
}

static inline bool qFuzzyCompare(float p1, float p2)
{
    return (qAbs(p1 - p2) * 100000.f <= qMin(qAbs(p1), qAbs(p2)));
}

👉 https://doc.qt.io/qt-6/qtglobal.html#qFuzzyCompare

[kbw]

You should be using the epsilon for each type rather than hard-coded factors.

[Peter87]

I don't think there is a simple solution that is suitable everywhere.

Using an "epsilon value" might be necessary in some situations, but then you also need to decide what "epsilon value" should be used.

In a lot of situations it doesn't matter a whole lot if there are small rounding errors and there is no need to compare for exact equality. For example in a game the user is probably not going to notice if the player is 0.0001 pixels off, and if you feed real measurements to a program that does some calculation or simulates some real world process then you will have errors in your measurements which can often be a bigger source of errors than the floating-point numbers.

[jonnin]

there is probably a clean way to do it as integers (possibly faster comparison?) using something like this (which may have flaws, its a 10 cent hack to demonstrate the idea only!). Basically chopping off some of the significant digits and checking for equality that way, akin to does 0.10005 == 0.10004, it does if you chop of the last digit. Useful? Not sure. I was a little heavy handed taking off 3 bytes.

int main()
{
  double d{1};
  double d2{1};
  uint64_t* u= (uint64_t*)&d;
  uint64_t* u2= (uint64_t*)&d2;
  d2 = 0.0001984126984126985;
   d = 0.0001984126984126977078;  
  *u &= 0xFFFFFFFFFF000000ull;
  *u2 &= 0xFFFFFFFFFF000000ull;
  bool eql = *u == *u2;  
  cout << setprecision(19) <<d2 << sp << d << endl;
  cout << boolalpha  << eql << endl;
  cout << d2-d;
}

you may have to watch out for byte ordering on the logic, but again, its a quick
hack.

0.0001984126984098111279 0.0001984126984098111279
true
0

but, I don't know if the bit patterns really work like that correctly for all values. Probably not?

[seeplus]

I think that what's called 'a hackers' hack'!

[jonnin]

Sure, its awful. I don't even know if it works... I certainly don't trust it outside of sandboxing.

in graphics, a pixel is an integer unit. Graphics can be done in integers if you want. And most graphics can stand to fudge a little: you can't see tiny (1e-50!) mistakes even for things where it is high precision/medical/scientific/etc.

There is no reason for despair. First, you need a problem where standard doubles are not working due to their inherent flaws. Once you have that problem, you can review the solutions that others have come up with over the past 50+ years of computing with this type of value. If none of that works --- then you can start to worry a little before rolling up your sleeves and seeing what else you can do about it.

At the worst case, you can just roll out one with integers with an exponent. It will be slower, but that is the price we pay when we exceed what the hardware is capable of doing (same for big int, big double libs). A pair of integers where the first is ULL (18 decimal digits of precision) and the second is where the decimal goes. Comparison is exact, if you are willing to pay the performance cost.

[zapshe]

I tend not to run into this issue. Comparing doubles works good enough usually. While it has happened to me before, there's always a solution on a per-case basis.

Push comes to shove, I'd just use C# if it was that important and the project didn't require C++.

C#:

decimal u = 0.1m + 0.1m + 0.1m;
decimal v = 0.3m;
Console.WriteLine(u == v);

True

[jonnin]

specifically for comparisons, you don't run into it unless you find a bug where it took the wrong path. How often do you really notice that nearly equals too the not equals branch? Only if looking for it... because of a bug ...

[JLBorges]

#include <iostream>
#include <limits>
#include <iomanip>
#include <cmath>

int main()
{
    std::cout << std::fixed << std::setprecision( std::numeric_limits<double>::digits10 ) ;

    const double d = 1'000'000.0 ;
    const double first = d  - 0.000'000'1 ;
    const double second = d + 0.000'000'1 ;

    std::cout << "compare " << first << "\nand    " << second << '\n' ;

    // 1. absolute difference
    std::cout << "absolute difference: " << std::abs(first-second) << '\n' ;


    // 2. relative difference: the general method to check if two values are 'close enough'
    // but it may bomb horribly in the presence of catastrophic cancellation
    std::cout << "relative difference: "
              << std::abs(first-second) / std::min( std::abs(first), std::abs(second) ) * 100.0 << " %\n" ;
    // TO DO: handle special cases (zero, NaN, inf, denormalised)


    // 3. float distance: count of how many representable floating-point values lie between the two values
    // an accurate measure, but usable only when the two values are expected to be very close to each other
    const double lower = std::min(first,second) ;
    const double higher = std::max(first,second) ;
    unsigned long long dist = 0 ;
    for( double from = lower ; from < higher ; ++dist ) from = std::nexttoward( from, higher+100 ) ;
    std::cout << "float distance: " << dist << '\n' ;
}

https://coliru.stacked-crooked.com/a/b1b5265ac36d2bae