Re: Comparisons and decorations
Arnole Neumaier wrote:
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 think there is a SERIOUS misunderstanding going on here.
NO ONE is advocating that Overflow should be represented by RealMax!
The idea is that Overflow would be something like a "decorated
floating-point infinity." New and special rules to the IEEE 754 arithmetic
would then be required to compute with this value properly. If such a change
was (had been) made to the IEEE 754 arithmetic, there would be benefits to
implementations of IEEE 1788 arithmetic.
From a conceptual point of view, this would be the same as leaving the IEEE
754 arithmetic "as is," decorating the interval [1,Infinity] with an
IsBounded decoration, and then using special routines to "fix" the endpoint
results that are incorrectly produced by existing IEEE 754 arithmetic.
The important differences (benefits) are in how the underlying interval
arithmetic operations are potentially implemented... not the definition of
interval arithmetic itself as we've already accepted in Motion 5 (that would
NOT change).
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.
That's pretty clever, and not too bad an idea.
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?
I don't think its so bad.
I still like Ulrich's better (it is still simpler and more efficient), but
yours is not so bad, either.
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.
That makes sense.
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.
I don't see it is an argument not to put comparision operators into the
standard, but otherwise I think I agree with what you've been saying.
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.
Arnold, with respect, you are still missing the previous point about
implementation of the underlying arithmetic operations.
Otherwise I think we actually begin to agree.
Nate
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.