Re: Some thoughts on Motion 19 (still under vote)
Dan Zuras Intervals wrote:
If, as Arnold believes, it is impossible to specify
acceptable behavior among some subset of the implicits,
they can be further deprecated or eliminated altogether
in some future motion. When that is known to be the
right thing to do.
This can already be known today.
Strange things happen already in very simple situations.
Here is an example how inclusion monotony can fail in finite-precision
midrad arithmetic.
For simplicity, it is illustrated for an underlying
arithmetic with base 10 and just two significant decimal digits,
and rounding to nearest, if ties are broken randomly or towards even
(but also with rounding towards infinity). One can easily create similar
situations with binary arithmetic and more significant digits.
Let xx=(0+-1.5). Then
xx + (2+-0) = (2+-1.5)
without overestimation, since the result is exactly representable.
The infsup form of the result is [0.5,3.5].
Upon splitting the box xx in the middle, we get two intervals
yy=(0.75+-0.75) and zz=(-0.75+-0.75); again without overestimation.
Now if we perform the same operation with yy in place of xx, we get
in exact arithmetic
yy + (2+-0) = (2.75+-0.75),
but due to the finite precision, this may be rounded outward to
(2.8+-0.80).
The infsup form of the result is [2.0,3.6], which is _not_
contained in [0.5,3.5].
Thus finite-precision midrad addition need not be inclusion monotone,
although the enclosure property is not violated.
It is a matter of judgment whether this is deemed acceptable.
In this example, one could redeem the situation by rounding towards
zero. But currently no theory exists to ensure the absence of similar
issues in other examples, or for other operations or elementary
functions.
I can only point out the dangers that I can see, and there are not
few of them....
Upon splitting yy again in the middle, we get in exact arithmetic the
two intervals aa=(0.375+-0.375) and bb=(1.125+-0.375). In
finite-precision arithmetic, this becomes
AA=(0.38+-0.38), BB=(1.1+-0.38).
Due to the overestimation, a branch and-bound process will handle twice
all numbers in [0.72,0.76] both in the AA branch and in the BB branch.
Note that with the radius represented by few bits only, wide intervals
such as [0.72,0.74] with this ''doubled'' behavior are likely to occur
in similar examples even when midpoints are representable with high
accuracy.
In higher dimensions, this effect may lead to an artificial exponential
explosion of the work.
It is again a matter of judgment whether this is deemed acceptable.
In my judgment, it is not.
In any case, standardizing midrad
-- without an adequate prior support through extensive experience
with a midrad implementation and a theoretical analysis of the
properties in finite-precision arithmetic --
means buying a pig in a poke.
It is _very_ difficult to predict in advance all possible such
anomalies.
Thus whatever the standard would be specify on midrad behavior
might later turn out to have unwanted consequences.
But a standard should increase the safety of use, and not invite
unpredictability of its consequences.
It is simply a decade too early to standardize midrad behavior.
Arnold Neumaier