OOPS Re: [std-interval] Interval comparison operators

R. Baker Kearfott rbk at louisiana.edu
Wed Apr 26 12:51:45 PDT 2006

```Guillaume et al,

OOPS, I meant my correction to read:

Didn't you mean
- false if for every x in X and y in Y,  x >= y,

???

Otherwise, it includes the case of overlapping intervals.

Baker

>Date: Wed, 26 Apr 2006 11:49:11 -0500
>To: std-interval at compgeom.poly.edu
>From: "R. Baker Kearfott" <rbk at louisiana.edu>
>Subject: Re: [std-interval] Interval comparison operators
>
>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
---------------------------------------------------------------

```

More information about the Std-interval mailing list