[std-interval] Interval comparison operators

[Guillaume Melquiond]

Hi,

On the last draft of the proposal I posted, I had removed everything
related to interval comparisons because we felt this needed some more
work. Before tackling this issue, we would like to get your opinions on
the subject of comparing intervals.

For those who did not get to read our very first proposal, I will detail
what our approach was, so as to have a starting point for discussing.
The operators on intervals were directly derived from the order on real
numbers. Given two intervals X and Y, the result of (X < Y) was defined
as:
  - false if there are some values x in X and y in Y such that x >= y,
  - true if x < y for all the values x in X and y in Y,
  - a thrown exception if the intervals overlap or are empty.

As a first consequence, it reduces surprise for developers since a
property like (X < Y) == !(X >= Y) always holds true. But this is not
why we chose this definition in the first place. We wanted generic code
to be usable with intervals. Let's consider the following toy example:
computing accurately the sign of a 2x2 determinant. A generic C++
template implementation would look like:

        template< class T > sign_t det2(T a, T b, T c, T d) {
          T u = a * d, v = b * c;
          if (u < v) return negative;
          if (u > v) return positive;
          return zero;
        }

Now let's try to compute the sign of a floating-point determinant.
det2<double> is a fast but not reliable implementation. det2<exact>
(with "exact" being an exact arithmetic type) is reliable but slow. The
following implementation is generally fast and always reliable:

        sign_t good_det2(double a, double b, double c, double d) {
          try { return det2< interval<double> >(a, b, c, d); }
          catch(...) { return det2< exact >(a, b, c, d); }
        }

So first an interval evaluation is done, and if the result is not
guaranteed, an exception is thrown during the first comparison in the
generic code and the specific code falls back to the exact evaluation.
This example was inspired from the arithmetic filters of computational
geometry. Only generic code has to be written and it can then be used
with interval arithmetic to produce guaranteed results.

Now people may be reluctant to use exceptions (because of runtime cost,
code complexity, and so on) when specifically designing an interval
code. So, in our proposal, the comparison (X < Y) does not directly
throw; an exception is thrown only when the result of a comparison is
converted to a boolean value, for example in an "if" conditional
expression. This allows for other ways of comparing two intervals.

In particular, interval libraries usually provide explicit functions for
comparing intervals, something like "certainly less than" or "possibly
less than" functions that would always return a boolean value and never
throw. We believe C++ features should be used to provide a nicer syntax
though. Instead of cerlt(X,Y), a "certainly less than" comparison would
then be written as:

        if (certainly(X < Y)) ...

This should make a rather detailed overview of our opinion on comparison
operators for intervals. Now we are interested in what the opinions of
other interval developers are. Should the user be allowed to compare
intervals in C++? And if so, what should the semantic of these
comparisons be?

Best regards,

Guillaume