[std-interval] Interval comparison operators

[R. Baker Kearfott]

Guillaume et al,

I am glad you brought this point up again.

You are proposing an interesting way of handling the "three-valued"
logic of interval comparisons within existing boolean language
constructs.  I'll be interested in seeing what others think about it.

Actually, I have a small (possible) correction to your explanation.
You had:
>  - 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.

Didn't you mean
   - false if there are ANY  values x in X and y in Y such that x >= y,

???

Best regards,

Baker


At 06:06 PM 4/26/2006 +0200, Guillaume Melquiond wrote:
>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
>
>_______________________________________________
>Std-interval mailing list
>Std-interval at compgeom.poly.edu
>http://compgeom.poly.edu/mailman/listinfo/std-interval
>
>

---------------------------------------------------------------
R. Baker Kearfott,    rbk at louisiana.edu   (337) 482-5346 (fax)
(337) 482-5270 (work)                     (337) 993-1827 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
(Room 217 Maxim D. Doucet Hall, 1403 Johnston Street)
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------