Re: Comparisons and decorations
> Date: Fri, 24 Sep 2010 18:31:31 +0200
> From: Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
> To: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>,
> 1788 <stds-1788@xxxxxxxxxxxxxxxxx>
> Subject: 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.
Well, for any predicate that depends on the truth
(or falsity) of a comparison like a < b, that can
be turned into a <= b by rounding errors.
I'm pretty sure people will want to be able to
test interval1 < interval2. And its compliment.
>
> 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.
I believe that is true.
Still, the opposite assertion, that two intervals have
a common intersection is also an important test. In that
case rounding errors can create a common intersection
where none really exists.
>
>
> 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.
It kind of depends on how you define these things.
In general, I believe assertions based on <= are
more robust than assertions based on <.
I will illustrate why below.
>
> 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.
Only in so far as we are counting on a <= b never
becoming a > b when a & b go through the same
calculations.
>
>
> > 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.
Hmm. Perhaps I misunderstand then. I thought there
were narrowing algorithms which counted on the
continued intersection getting narrower. Namely that
xx(i+1) \interior xx(i) at each stage. Or at least
each stage was confined to xx(i+1) \intersect xx(i).
Do I have that wrong?
>
>
> Arnold Neumaier
For the above concerns, let's say we have aa(0) =
[alo(0),ahi(0)] & bb(0) = [blo(0),bhi(0)] & we implement
the predicates
disjoint(aa,bb) = (ahi < blo) || (bhi < alo)
contained(aa,bb) = (blo <= alo) && (ahi <= bhi)
Now let's start with ahi(0) < blo(0) so that disjoint is
true & contained is false.
It is easy to see that as we go along in calculations
producing first aa(1) & bb(1) then aa(2) & bb(2) & so on,
that there may come a time when we no longer have
ahi(i) < blo(i) but ahi(i) == blo(i).
Then disjoint would become false & contained would remain
false.
But the admonition against two calculations changing their
a <= b status goes away when you ROUND THEM IN DIFFERENT
DIRECTIONS.
Therefore it is even possible that there may come an i'
such that ahi(i') > blo(i') & the two intervals would
appear to have some overlap.
Still not too bad as Arnold points out.
But there is a more subtle problem lurking here.
Even when you round in the same direction & we know
that alo(0) <= ahi(0) < blo(0) means that we can
count on alo(i) <= blo(i) for all time, it is possible
that blo(i) will go through a series of roundings that
cause it to move much faster & farther than alo(i).
It is just possible, therefore, that eventually we
will come to an i'' such that alo(i'') == blo(i'').
Should that come to pass we will have both disjoint
being false & contained becoming true.
So we will have gone from
disjoint(aa(0),bb(0)) = true &
contained(aa(0),bb(0)) = false
to
disjoint(aa(i''),bb(i'')) = false &
contained(aa(i''),bb(i'')) = true.
I don't know if this constitutes a danger to a correctly
written interval program but as I believe we want both
predicates in our arithmetic, it must be accounted for.
I guess thats $0.02 more. :-)
Dan
P.S. - I've been thinking about this analysis & I may be
wrong here. It is easy to come to the i' case but I am
having a harder time constructing the i'' case in my head.
So Arnold might be right after all in that contained
might not go from false to true. Let me think about it.
P.P.S. - Nope. Forget about it. I can do the i'' case
in one step. It is possible. For a hint it involves
crossing a binade or decade.