Why is 0..2 < 1..3 true?

[dataopt]

I was surprised to see the following:

julia> 0..2 < 1..3
true

In Introducton to numerical analysis by Neumaier (p.40) and Introduction to Interval Analysis by Moore, Kearfott and Cloud (p.9), it is defined that [a,b] < [c,d] iff b < c. So I am a bit puzzled that Julia would return true for [0,2] < [1,3]. Is this a bug or a different definition of < used by the package?

[lbenet]

Thanks for opening the issue! There have been some discussions around this: see https://github.com/JuliaIntervals/IntervalArithmetic.jl/issues/165 and https://github.com/JuliaIntervals/IntervalArithmetic.jl/issues/168.

The IEEE-1788 standard distinguishes the functions less, preceedes, strictless and strictprecedes (cf. Table 10.3). less corresponds to our implementation of ≤, and strictless to < which correspond to a weak definition, as you point out in your comment. The definition you include above corresponds to strictprecedes, while if you include the equality it is precedes.

julia> a = 0 .. 2
[0, 2]

julia> b = 1 .. 3
[1, 3]

julia> a < b
true

julia> strictprecedes(a,b)
false

You should have a look to NumberIntervals.jl, which provides the functionality of IntervalArithmetic, being more cautions in certain situations, such as using <.

[lucaferranti]

short answer: because the IEEE-1788 standard for interval arithmetic says so (although to be fair the standard just says that there should be such a function and suggests the symbols <, <= but we could use different ones).

long answer: defining comparison of intervals is kind of tricky as there is no unambiguous way of doing it. Before the standard, there were several options:

• certain policy: this is what you pointed out [a, b] < [c, d] <=> b < c, this is equivalent to being true if it's true for all elements in both intervals
• possible policy: return true if it's true for at least one element in the first interval and one element in the second
• ternary: return missing for ambiguous cases
• boolean: uses "boolean intervals" [true, true] for certainly true, [false, false] for certainly false and [false, true] for ambiguous cases.

Most "non-standard-compliant" interval arithmetic libraries (Gaol, Filib++, boost) support these kind of behaviors. Note that these libraries were created before the standard (it is good to highlight that the standard is very young, 2015 and most interval arithmetic libraries are not compliant)

Now you are probably wondering, if we had a set of already existing options, how did we end up with a completely new one that (apparently) makes most people unhappy?

My summary above follows what was discussed in the vienna proposal, basically people working towards a standardization of interval arithmetic met in vienna, discussed and came up with a proposal for the standard. In this proposal the main suggestion (section 5.4) was to have the certain policy as default and other policies as optional.

A reply to the vienna proposal can be found in this paper, where the overlap operator, inspired by Allen's interval algebra from temporal logic is used to define all possible comparison cases of intervals (interval arithmetic overlap is basically the 13 cases of allen's algebra + 3 special cases for empty intervals). If you look at table 3 you will find the comparison [a, b] < [c, d] <=> a <c && b < d as defined in the standard.

You may still be wondering why the <, <= are defined that way. This is due to the work of Ulrich Kulisch, who proposed an axiomatic theory of computer arithmetic and interval arithmetic. Kulisch showed that defining the comparisons the way they are defined in the standard gives some nice algebraic structures, e.g. that (IR, <=) is a complete lattice (IR being the set of real intervals), meaning every subset has a least upper bound and a greatest upper bound). This standard definition of comparison is also in a way coherent with the set-like definition of equality [a, b] == [c, d] <=> a == c && b == d. Kulisch theory of interval arithmetic is deeply discussed in chapter 4 of his book "Computer arithmetic and validity", which is a very nice read that I can warmly recommend (you can see I'm an interval geek :) )

Now the final questions Is Kulisch work impressive and valuable? Definitely! Should a practical implementation of interval arithmetic follow it? I don't know. I don't know how likely the standard is to change in the future, but I think that if something will change, it will be the guidelines for comparison.

Final comment: when is any of this relevant? Interval arithmetic has mainly two applications:

1. verified floating point computations (meaning your intervals radii are generally ~1e-16, at least at the beginning of the computation), for this application it is tempting to think of intervals as a replacement for real numbers (because each interval is close to singleton), in this case most of your intervals will be disjoint anyway (and all definitions above will agree), for the (rare) pathological cases when intervals will overlap (e.g. cluster of almost multiple eigenvalues, huge loss of precision) then it probably makes sense to use a ternary logic (which will return a non-bool and hence break the code) or the certain policy (which will not break the code but is safe)
2. uncertainty propagation: in this case you start with "wide" intervals, e.g. you have 10% uncertainty or your measurement or you have a set bounding the initial state of a dynamical system and you want to propagate that. In this case, it just makes no sense to plug intervals in a code written for reals and hope it will work. Best case scenario, it will probably return uselessly large intervals, worst case scenario, it will error anyway. Also, if your code relies heavily on comparisons, then it's not meant to be used with intervals and what you really want to do is to study the algorithm, the numerics and design an interval generalization of it (which is also pretty fun actually)

[lucaferranti]

(the previous comment mutatis mutandis could probably be added to the documentation as the standard comparison definition is pretty surprising for many)

[dataopt]

Thanks to all who responded. Indeed, such points would be very valuable when added to the documentation.