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

Question

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{};

Customer

even a simple return lhs < rhs; breaks strict-weak-ordering when the numbers can be NaN – Onofredo

@phuclv: I wanted to cover that concern by "in comparison to regular std::less" :-) – Customer

Related to floating-point-keys-in-stdmap – Customer

Answer 1

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

4. 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.

Customer

Note that the question specifies < epsilon, not <=. Trivial fix : {x,y,z}={0,epsilon/2, epsilon}. – Mott

@MSalters: 0 and epsilon are actually equivalent. class is Less, not Equal. – Customer

Why asking question if you were able to provide answer in exact same time (less then minute difference)? – Jecoa

@MarekR I believe there is an "answer your own question" checkbox under the question draft that allows you to write an answer before posting the question, so both question and answer get posted at the same time (I've never personally tried it though, so I might be wrong about something). – Conchoid

@Conchoid you missed the point. I'm not asking about SO features, but it is strange to ask for help which is not needed, state question when answer is known ahead. Is this some kind of documenting real word question for example from lectures in collage? – Jecoa

@MarekR: During review, I saw that problem. My coworker asked for reference, and I didn't find direct answer for that, So I create that answer (which I think might help others). – Customer

Answer 2

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.

Convalesce

In which domain LessWithEpsilon would be usable? One from which x + epsilon == x, (so regular std::less is still preferable). – Customer

@Customer Consider for example set of values 1, 1.5000001, 1.5 and epsilon of 0.1. First would compare less to the last two which compare equal. The elements are in a strictly weak order. – Convalesce

By "Domain", I understood ranges, not subset of points :-) – Customer

@Customer yeah, it has to be a set of ranges. Each disjoint range has to compare equal within the range, and has to compare unequal to other ranges in order to be orderable by that function. – Convalesce

Are you proposing something like std::make_tuple(std::is_nan(lhs), std::isfinite(lhs) ? std::fmod(lhs, eps) : lhs) < std::make_tuple(std::is_nan(rhs), std::isfinite(rhs) ? std::fmod(rhs, eps) : rhs)? – Abernon

@Abernon I didn't actually have a suggestion of what to use, but I think I will. – Convalesce

@Abernon I've added a proposal for what to use. – Convalesce