Re: Comparisons and decorations
> Subject: Re: Comparisons and decorations
> From: John Pryce <j.d.pryce@xxxxxxxxxxxx>
> Date: Sat, 25 Sep 2010 16:48:40 +0100
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> Nate
>
> On 24 Sep 2010, at 11:48, Arnold Neumaier wrote:
> > Nate Hayes wrote:
> >> 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).
>
> Looking at 754-2008 §5.3.1, I think
> (nextDown(al) >= bl) and (nextUp(au) <= bu)
> also works, since nextDown(-oo) = -oo and nextUp(+oo) = +oo.
>
> John Pryce
If the intention is that interior is subset with a
smidge at both ends except when that end is infinite,
then both formulas have performance problems.
The first risks NaNs on the subtracts (which compares
false so the formula has the correct outcome). But
because of our decorations, implementations may end
up running with the invalid trap enabled which slows
things down by factors of 100x to 1000x when it
happens.
(HP ran into this problem once under slightly
different circumstances & suffered a 6% hit on a
benchmark because it was happening only very rarely
in a loop. Good thing too because the hit was 300x
on our machine each time it happened.)
John's formula is correct & doesn't suffer from this
problem but suffers from another. All systems that
I am aware of implement nextAfter (he precurser to
both nextUp & nextDown) in software. We made nextUp
& nextDown independent of nextAfter in 754-2008.
Still, chances are they will be implemented in
software as well. Another performance hit I'm afraid.
Let me suggest a more explicit implementation:
interior([al,au],[bl,bu]) ==
((bl < al) || (bl == -infinity)) &&
((au < bu) || (bu == +infinity))
There are 4 tests involved but they are all done in
hardware. In addition, if they are written in this
order usually only 2 or 3 of them will be executed.
Let me see if I can do the case analysis:
(1) bl < al = true, bl == -oo not needed,
au < bu == true. bu == +oo not needed,
2 comparisons.
(2) bl < al = true, bl == -oo not needed,
au < bu == false. bu == +oo needed,
3 comparisons.
(3) bl < al = false, bl == -oo false,
rest not needed,
2 comparisons.
(4) bl < al = false, bl == -oo true,
au < bu == true. bu == +oo not needed,
3 comparisons.
(5) bl < al = false, bl == -oo true,
au < bu == false. bu == +oo needed,
4 comparisons.
I think I have that right. By far the most common cases
will be (1) & (3) which only require 2 comparisons.
So the average case should be in the 2+epsilon range.
But even the other cases will all be done in hardware
with no traps involved so no big hits.
Just a suggestion...
Dan