(j3.2006) Interval arithmetic

[Van Snyder]

On Wed, 2009-03-18 at 22:59 -0700, Malcolm Cohen wrote:
> > Well look again for yourself if you don't believe Christian Keil or any
> > of the other members of P1788.  The packages existed, but were found
> > _not_ to work.
> Except of course when they did.  At least they were claimed to at the 
> time, and I have no doubt whatsoever that they did work - at least the
> ones using NEAREST rather than the nonexistent rounding mode fiddles.
> P1788 can say that these didn't work because of rounding until they're
> blue in the face, but that doesn't make it true because in fact those 
> ones DID work.

In interval arithmetic, "work" means "the bounds always enclose the
exact mathematical answer -- no exceptions."  If it can be shown that a
bound returned by an interval calculation does not enclose the
mathematical answer, the program didn't work.  It doesn't matter if it
works on millions of other problems.  If it fails on one it doesn't
work.

According to members of P1788, there have been packages that produced
intervals that failed to enclose the mathematical answer because a value
had been calculated in higher precision than the program specified,
rounded to a precision chosen by the processor but different from the
precision implied by the operands and operation, carried by the register
allocator to a place in the program having a different rounding mode
from where the calculation was done, then rounded to the precision
specified by the program using the wrong rounding mode.  The only way
they were able to repair them was to send results through volatile
variables, to force values to be rounded to the precision specified by
the program before the rounding mode was changed.

Before rounding-mode specifications were available, interval bounds were
rounded explicitly by using max(tiny,top+abs(top)*epsilon) for the upper
bound and min(-tiny,bot-abs(bot)*epsilon) for the lower bound.  More
expensive schemes that produce tighter bounds were also used.  These
work because the compiler doesn't fiddle the value of epsilon according
to the precision it has chosen for the intermediate result, while
rounding in hardware does effectively use a value of epsilon specific to
the precision the processor has chosen.