Re: Comparisons and decorations
> Date: Fri, 24 Sep 2010 12:48:38 +0200
> From: Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
> To: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
> CC: John Pryce <j.d.pryce@xxxxxxxxxxxx>,
> stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
> Subject: 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.]
>
> >>>>> . . .
>
> 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.
>
> > . . .
>
> ??? 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.
>
> > . . .
>
> What is so bad about the above definition?
>
> >> . . .
>
> 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.
>
> . . .
>
> > 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.
I believe that Arnold has a good approach here.
In addition, it has some aspects to it that we
first discussed when decorations were introduced
as an approach to exception handling.
One of those principles was that, in an arithmetic
operation, the interval part of a decorated result
should only depend on the interval parts of the
decorated operands. Whereas the result decoration
could depend on all of the interval parts of the
operands, their decorations, & the operation itself.
The reason for this was efficiency. We did not
want any interval hardware to have to look at
decorations to decide the value of its results.
It would slow the pipeline in a deep pipe machine.
We could not extend this principle to the results
of all predicates. For indeed, how would one deal
with IsDefined(xx)?
But it seems reasonable to me to extended it to
those predicates that THEMSELVES depend on the
interval parts of their operands. Predicates like
LessThan(), Equal(), & Interior().
So if, as I see above, Arnold is proposing that
predicates like Interior() depend only on their
numerical comparisons & not on decorations like
Overflow or IsBounded, I think that is a good
thing.
It is a reasonable extension to ask that numerical
predicates ALSO be efficient in an execution pipe.
After all, branches will result from this. Not the
rare & exceptional branches of IsDefined() & its
friends. But the common branches that need to be
done fast in loops.
Finally, on the issue of false positives.
I don't think this can be prevented on ANY predicate.
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.
Therefore, in any Predicate(xx) or dyadic relation
xx \Related yy, it is possible that the outcome may
be changed by the numerical expansion of its operands.
The Predicate(xx) may stray into its danger zone. Or
one operand in xx \Related yy may expand more than the
other (but only in limited ways).
It cannot be prevented.
Remember also that rounding errors are not random.
Nor are they distributed randomly in any given string
of 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.
There is a saving grace, however.
Arnold's observation above about 754 arithmetic stems
from the fact that, in 754, if we know in advance of
an operation that a < b then it is true after an
operation that a Op c <= b Op c (or the moral
equivalent in the case of c / a >= c / b).
Therefore it will never be the case that one interval
'passes' another due to numerical error.
In 754. I cannot comment on other arithmetics.
We went to a great deal of trouble to make that true.
So if we make our comparisons & predicates along these
lines & NOT depend on decorations, we should be fairly
safe.
Just my $0.02 worth.
Dan