Re: Comparisons and decorations
Dan Zuras Intervals wrote:
Date: Fri, 24 Sep 2010 12:48:38 +0200
From: Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
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.
. . .
Finally, on the issue of false positives.
I don't think this can be prevented on ANY predicate.
For many predicates it cannot be prevented, and this is
sufficient reasons to ban them from the standard.
For the three predicates that matter, it _is_ possible to the
extent needed without any difficulty. And it is _necessary_
for interval algorithms to make decisions. Therefore it _must_
be ensured by any standard that deserves its name.
Remember we are computing our intervals within an
arithmetic of finite precision & range. Therefore,
we risk expanding our intervals beyond their strict
range every time we touch them. Sometimes by a
little. Sometimes by a lot. It depends on both the
operations involved & the precise values of its
operands.
Disjointness can only change from true to false by overestimation.
Thus overestimation is harmless, since it does not introduce false
positives.
Containment and interiorness can only change from true to false
when the first argument is overestimated. Thus this is harmless,
since it does not introduce false positives.
But it can be changed from false to true when the second argument
is overestimated. Thus this is potentially dangerous, since it may
introduce false positives. However, in the applications, the second
argument is always a fixed interval _known_ not to be overestimeated.
Thus (once the semantics is precisely defined), users cannot go wrong
in applying it as long they adhere to the semantics.
Nothing can save users from applying constructs outside of their
defined semantic meaning; so we don't need to care for that.
We only need to ensure that the semantics comes clearly and
unambiguously across, and this is the case the shorter and the more
conceptual the formulation.
Remember also that rounding errors are not random.
Nor are they distributed randomly in any given string
of calculations.
This does not matter at all in the present context.
So, even in the case of xx \interior yy where both xx
& yy typically go through the SAME calculations to
arrive at the comparison, one may have expanded a
great deal more than the other.
In those applications where this needs to be checked, to get an
existence assurance of a zero, say. yy does not suffer any
overestimation since it is an interval _chosen_ by the user
(or algorithm) to mean this domain, not to mean a computed range.
Arnold Neumaier