Comparisons and decorations
In [Re: Motion P1788/M0013.04 - Comparisons], Nate Hayes raised
an important issue about comparisons and decorations that has much
more general impact than apparent from his particular example:
How do decorations influence the outcome of comparison relations?
This must be decided unambiguously, and in a way consistent with
the uses of decorations for guaranteeing correctness of interval programs.
Below is my proposal for handling this issue correctly.
Arnold Neumaier
=========================================================================
Nate Hayes wrote:
Arnold Neumaier wrote:
[etc.]
So this approach seems to retain all the important advantages of
unbounded intervals without actually introducing the complications
that arise from them.
Could you please point to a real complication of the implementation
that Inf in place of OVR produces?
This has already been done recently, in regards to discussions about
implementation of the arithmetic operations, e.g.,
[1,Overflow]*[0,0]=[1*0,Overflow*0]=[0,0]
etc.
But this does not execute in IEEE 754 as Overflow must be larger
than the largest machine number. So there is no saving compared to
using Inf in place of Overflow - one still needs a branching operation.
Since one also needs to ensure that Overflow*finiteNumber = Overflow,
one also hasn't the option to use RealMax in place of Overflow.
In summary, Using Overflow dfoes not give an implementation advantage
over Inf when using 754 arithmetic. On the other hand, if 754 arithmetic
is modified for directed rounding according to the recommendations in
the final Section of the Vienna proposal then 0*inf = inf in roundup
mode, and one has exactly the behavior you want to have for Overflow.
Therefore there is no advantage at all in considering Overflow.
I also think Ulrich's comparision relations are very good from a
computing perspective, since they are very simple and efficient to
implement in both software and hardware. However, John's definition for
interior will require a much more complicated implementation of this
comparision operation, since it will require checking special cases for
A \interior B
such as when A and B are both Entire or A=[1,Infnity] and
B=[0,Infinity]. In these cases, the interior operator would need to
return a different result than when A and B are compact intervals, such
as A=[1,100] and B=[0,200].
??? There is a uniform formula in 754:
[al,au] interior [bl,bu] iff ~(bl-al>=0) and ~(au-bu>=0).
Since one does not check interiorness very frequently (compared to other
arithmetic operations), the two extra nots are immaterial for efficiency.
I would not care so much about unbounded intervals if there was another
suitable definition to justify A \interior B as defined by Ulrich. If
the mathemeticians could figure out if this can be done, I'd be happy
with that as a solution.
What is so bad about the above definition?
For me it mainly looks like a change of names messing with
the conceptual meaning of intervals but introducing no visible gain.
Well, you had been advocating an IsBounded decoration. What is the
meaning of
[1,Infinity] \subseteq [1,Infinity]
if both intervals have the IsBounded decoration?
We hadn't yet discussed the behavior of decorations for nonarithmetic
operations; Motion 8 was silent on these, but in the present context
it must be decided. The rationale is as follows:
Decorations are primarily there to allow making decisions about
nonexistence, existence, and uniqueness correctly. This is the only
place where I think they are essential for the correctness of interval
programs.
Therefore, one needs to ensure that a test for disjointness,
containment, or interiorness, is never false positive.
This rule is enough to decide all ambiguities for these
three comparisons.
In particular, in your query, defining the result to be false is
the only consistent choice.
On the other hand, this does not solve the ambiguities for the
other comparison operators currently under discussion/voting.
This is an excellent reason for _not_ putting these operators into
the standard.
It seems to me this is the same as
[1,Overflow] \subseteq [1,Overflow]
yes, the same problems arise, nothing is gained by using Overflow
in place of Inf.
A standard should not require new research but take stock of what
exists already in a good state, and select from that.
The worst thing about this suggestion is that it compromises
Motion 3 by weakening the conceptual correspondence of intervals
with definite sets, for the sake of at best a very slight gain
and at the cost of other difficulties introduced.
Even if P1788 does not want to include Overflow, but instead wishes to
include the IsBounded decoration, these questions will need to be solved.
I think the above proposal adequately solves the issue.