Does using epsilon in comparison of floating-point break strict-weak-ordering?

user_2684539 0
Viewed 183

Does following class breaks strict-weak-ordering (in comparison to regular std::less (So ignoring edge case values such as Nan))

struct LessWithEpsilon
{
    static constexpr double epsilon = some_value;
    bool operator() (double lhs, double rhs) const
    {
        return lhs + epsilon < rhs;
    }
};

LessWithEpsilon lessEps{};
epsilon strict-weak-ordering floating-point c++
2 Answers

From https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings

  1. Transitivity of incomparability: For all x,y,z in S, if x is incomparable with y (meaning that neither x < y nor y < x is true) and if y is incomparable with z, then x is incomparable with z.

Similarly, from https://en.cppreference.com/w/cpp/named_req/Compare

If equiv(a, b) == true and equiv(b, c) == true, then equiv(a, c) == true

With {x, y, z} = {0, epsilon, 2 * epsilon}, that rule is broken:

  • !lessEps(x, y) && !lessEps(y, x) && !lessEps(y, z) && !lessEps(z, y) but lessEps(x, z).
  • equiv(x, y) == true and equiv(y, z) == true but equiv(x, z) == false (as x + epsilon < z)

So, that class breaks strict-weak-ordering.

user_26845390

It is true that LessWithEpsilon does not impose a strict weak order for the domain of all doubles, as explained in Jarod42's answer.

However, there can be cases where the input has a limited domain of values for which LessWithEpsilon can impose a strict weak order. In particular, if the input consists of set of disjoint ranges where values of each range are equal to each other (within epsilon) and unequal to all other ranges (distance between ranges greater than epsilon).

In case you're wondering whether it is reasonable to consider limited input domains, consider that std::less also doesn't impose a strict weak order for domain of all doubles - NaN must be excluded.

As for what may have been the intention when writing the comparison function, I suggest a possible alternative: Transform the inputs such that each value is rounded to nearest multiple of epslon. This would technically make the input valid for the suggested comparison function, but it also makes it unnecessary because we would get same result using std::less.

user_20793030
Related