Interval comparisons may make other packages functions behave unexpectedly

[Kolaru]

Comparisons (==, >, <, etc.) between intervals or comparisons between intervals and numbers are possible, and run smoothly and silently, but they may behave in ways that may not make sense for the algorithm used.

As a simple illustration, a decent implementation of sinus cardinal (sin(x)/x) may be

function sinc(x)
    if x == 0
        return one(x)
    else
        return sin(x)/x
    end
end

But

julia> X = -0.001..0.001
[-0.00100001, 0.00100001]

julia> sin(X)/X
[-∞, ∞]

because X != 0 (correct result is [0.999998355066745, 1]).

In particular this makes many functions of SpecialFunctions.jl behave incorrectly, and it may be the reason behind this issue.

A possible way to mitigate it, beyond documenting it, may be to implement a debug mode that raise a warning whenever such comparison is performed.

[dpsanders]

I believe that the problem is not the comparisons, but rather using an if. Conditionals should be avoided with intervals exactly for this reason.

In general, "standard" algorithms will not work correctly for intervals. Writing interval versions of special functions is, unfortunately, often rather tricky.

[dpsanders]

In the particular case of sinc, you could e.g. use a separate Taylor expansion for the region near 0.

[dpsanders]

(And note that you should use one(x) instead of 1 for type stability.)

[gwater]

I'd like to propose the same solution I described here: Comparisons are inherently questions about numbers, not intervals. Therefore they cannot be decided in some cases. For example 1..2 < 3 can be decided but 1..3 < 2 has no meaningful answer.

So what do you think of this?

function <{T}(x::Interval{T}, y::T)
    x.hi < y && return true
    x.lo > y && return false
    throw(InexactError())
end

or, for two intervals:

function <{T}(x::Interval{T}, y::Interval{T})
    isbefore(x, y) && return true
    isafter(x, y) && return false
    throw(InexactError())
end

(Here I use isbefore() and isafter() in the sense of IEEE 1788-2015, Table 10.7.)

[lbenet]

I think questions like these, namely 1..2 < 3 or 1..3 < 2, are formulated considering intervals as sets. So, if the inequality holds for all members of the interval, you get true, otherwise false.

Note that there exist already the functions precedes, strictprecedes, islessprime, which I think are required by the standard.

[Kolaru]

I think questions like these, namely 1..2 < 3 or 1..3 < 2, are formulated considering intervals as sets. So, if the inequality holds for all members of the interval, you get true, otherwise false.

This interpretation is perfectly reasonable. Indeed, intervals are not numbers, therefore the fact that for example 1..3 < 2 and 1..3 >= 2 are both false is fine, even if it would never be the case for numbers.

However, one of the great things about intervals is that in most cases intervals behave as numbers. An awesome thing about this package is that it actually allows the user to use intervals in place of numbers without further modification, immediately giving correct results.

This is very convenient, but implies that Interval is a subtype of Number, i.e.

julia> isa(1..3, Number)
true

This suggests that with the current implementation intervals actually behave as numbers (which in general they don't).

Therefore, in my opinion, when it is not in contradiction with the standard, we should prefer the "convenient for user way" of having intervals that behave as numbers whenever it makes sense and otherwise throw an error. This is what the proposition of @gwater would enforce, and this overall strategy would guarantee that using intervals in place of numbers always yields correct results. (Note that correct does not implies useful, for example dividing by -1..1 actually yields a correct and in most cases useless result)

[oschulz]

How about making comparisons return an interval? If the result of the comparison is true for all possible values left and right of the comparison operator, the result would be something like Interval{Bool}(true, true). If false for all values, Interval{Bool}(false, false). Otherwise, the result would be Interval{Bool}(false, true).

This would automatically cause errors for if-statements on interval comparisons. And we could add a method to ifelse that supports Interval{Bool}, and depending on the boolean interval returns the result for true, or the result for false, or the minimum interval covering the both possible outcomes.

[gwater]

I've implemented an interval type based on IntervalArithmetic's intervals which behaves more predictable and cautious in comparisons. Feel free to upstream some methods. https://github.com/gwater/NumberIntervals.jl

[oschulz]

@gwater, I like that approach - are you planning to register NumberIntervals?

[oschulz]

Alternatively - maybe that new interval type could be integrated into IntervalArithmetic? @dpsanders, @gwater, what do you think?

[gwater]

@gwater, I like that approach - are you planning to register NumberIntervals?

After some testing interoperatibility with other packages a bit more, yes. Safe interoperatbility is really the main goal – are we able to use NumberIntervals safely with algorithms designed for Reals without the kind of silent failures IntervalArithmetic currently produces?

Alternatively - maybe that new interval type could be integrated into IntervalArithmetic? @dpsanders, @gwater, what do you think?

I think it's ok to have two separate packages for now: One for strict IEEE conform intervals (IntervalArithmetic), and one for Number-like intervals based on the former (NumberIntervals). Nevertheless, I would also welcome upstreaming NumberIntervals; or perhaps #271 will one day make NumberIntervals obsolete.

[dpsanders]

@gwater This looks great! Thanks for pushing through with this.

We should definitely look at how to incorporate this and/or #271.

[oschulz]

Can NumberIntervals be used with IntervalOptimisation? That would be awesome.

[gwater]

Can NumberIntervals be used with IntervalOptimisation? That would be awesome.

I haven't worked with IntervalOptimisation yet but I assume it is developed specfically for IntervalArithmetic's Interval and takes it's implementation details into account already. I made NumberIntervals for packages which outside the JuliaIntervals ecosystem and therefore unaware of the implementation details. Therefore I'm not sure what advantage replacing the interval type in IntervalOptimisation would bring.

[oschulz]

Therefore I'm not sure what advantage replacing the interval type in IntervalOptimisation would bring.

Well, my idea was that it would bring the advantages of NumberIntervals: No silent "wrong" conditional code paths taken due to comparison of intervals. The idea would be to be able to optimize generic user functions that are (not only) written for intervals - kinda like automatic differentiation can be used for generic Julia code. And at least fail in a predictable fasion if the code compares numbers and doesn't take the possibility of a "true or false" into account.

[dpsanders]

I think that the idea of using Cassette is a very interesting one.

But even so, there are certain types of numeric functions that could be handled, containing things like

if x < 3
  return x^2
else 
  return x^2 + 1
end

and others that are arbitrarily difficult, like

if f(x) < 0
  return x
else
  return -x
end

Determining whether f(x) < 0 for an interval is basically solving a root finding problem!

[oschulz]

I think that the idea of using Cassette is a very interesting one.

Uhm, I was actually thinking more on the lines of dual numbers and ForwardDiff as an analog. But sure, Cassette can do it, no question. ;-)

[Kolaru]

I've implemented an interval type based on IntervalArithmetic's intervals which behaves more predictable and cautious in comparisons. Feel free to upstream some methods. https://github.com/gwater/NumberIntervals.jl

That's great! I've had a look at it as I intend to (at last) resume my work on #271 and I think that returning a special object (either the custom Indeterminate or missing as in https://github.com/gwater/NumberIntervals.jl/pull/17) in ambiguous case is a good design choice that I'll definitely try to integrate here.

[oschulz]

Is the current approach to always return true for comparisons if they might be true useful in some applications? If not, I wonder if it would make sense to return Indeterminate() if the comparison result is not clear due to overlapping intervals, as suggested by @Kolaru (so comparisons would return a Union{Bool,Indeterminate}). Now that we'll be able to specialize ifelse with Julia v1.8, this would allow for writing generic interval-compatible code with decision points (see current discussion in gwater/NumberIntervals.jl#14). And if/else would fail instead of silently returning a result that the user may not expect.

[Kolaru]

Discussed in triage:

In the interest of simplicity and in the spirit of other recent decisions, the best course of action is probably to simply remove all these symbols for 1.0.