Re: Motion 8: Exception Handling for Interval Arithmetic
Dan Zuras Intervals wrote:
>> Date: Wed, 16 Sep 2009 11:33:20 -0400
>> From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
>> Subject: Motion 8: Exception Handling for Interval Arithmetic
>> To: STDS-1788@xxxxxxxxxxxxxxxxx
>>
>>
>> I submit the document "Exception Handling for Interval Arithmetic"
>> as a formal motion (motion 8) to be voted upon.
>>
>> The document presents a general framework for exception handling. It
>> uniformly accomodates all arithmetic and nonarithmetic exceptions
>> that ar= e
>> relevant for interval arithmetic and its applications. It eliminates
>> the need for separate global sticky flags, and integrates
>> non-intervals (NaI)= ,
>> without introducing any overhead for users who don't make use of
>> exceptio= ns.
>>
>> The document is attached as a PDF (4 pages) to facilitate its
>> reading. Th= ank
>> you to Arnold Neumaier for his joint contributions in writing it.
>>
>> Sincerely,
>>
>> Nate Hayes
>>
>
> Nate,
>
> This motion seems well thought out & well designed & I am
> inclined to be interested in something along these lines.
>
> Let me ask a few questions to clarify things.
>
>
> First, from the motion:
>
> 2.2. An operation on standard decorated intervals returns a
> standard decorated interval whose interval is the result of the
> operation on the argument intervals, and whose decorations are
> computed from the arguments such that they retain the most
> informative and valid information about the interval. All result
> decorations will be completely specified (later) according to
> the intended semantics of the decoration trits.
>
> This is excellent. The intervals only depend on the intervals.
> And the decorations may depend on both. This promotes (indeed,
> I would say, is essential for) efficient implementations.
>
> However, in the rationale, we have:
>
> 3.2. Recent discussion in the P1788 forum showed that some
> interval algorithms require decorated intervals while others
> only require intervals and/or decorations (or NaI's). There are
> various implementation and performance tradeoffs to be gained or
> lost by restricting interval computations to only one of these
> types of objects. These tradeoffs may depend on available
> (present or future) platforms, hence the choices should be left
> to implementors for exploitation, rather than be fixed by the
> standard.
> The framework presented in this motion also unifies the concept
> of NaI and Empty in a semantically correct way. For example,
> given any non-empty interval X,
> X \union Empty = X
> is usually the case. However, depending on the history that
> created Empty, some applications may need
> X \union Empty = Empty,
> which is the same semantics as NaI, i.e.,
> X \union NaI = NaI.
> This can be neatly handled by decorations.
>
> This example would seem to be the main desired result of the
> motion & yet it is an example where the interval result DEPENDS
> on the decoration of the operands.
>
Only indirectly. It is the forgetful operators that may essentially
accomplish this by throwing away some information (either the interval or
the decoration).
>
> Next:
>
> 2.3. An operation on bare decorations is obtained by promoting
> the bare decorations to decorated intervals whose intervals are
> the empty set and then performing the operation with the
> resulting decorated intervals.
>
> While I can admit the possibility that operations on bare
> decorations might be necessary, I can think of none.
>
> Is the intention here that things like test & set for
> decorations are done on the bare decorations rather than
> on the decorated intervals directly?
>
> Can you give possible examples of such operations?
All of the lengthy discussions about branch-and-bound algorithms are
examples, since in all those cases, the interval portion of a decorated
interval is no longer of any use once an exception occurs. Yet information
like "possiblyDefined" or "notDefined" must continue to propagate so that
the large blue boxes can avoid being chopped uselessly into tiny blue boxes,
etc.
John mentions a similar situation arises in interval ODEs in one of his
recent posts.
>
> Next:
>
> 2.4. An operation on bare intervals is obtained by promoting the
> bare intervals to decorated intervals whose decorations are all-
> 0 and then performing the operation with the resulting decorated
> intervals (if any further promotion rules are required, they
> will be specified and voted on in another motion).
>
> This is also good in that it seems the most prudent way to
> promote bare intervals to decorated intervals. Nicely done.
>
> Next:
>
> 2.5. Forgetful operations behave as specified above except they
> throw away either the interval or decoration portion of the
> result.
>
> And yet, since operations in 2.4 would seem to be 'maximally
> forgetful', I don't see the need for explicitly forgetful
> operations.
>
> Can you provide possible examples?
It is the branch-and-bound examples again, also supported by John's B1, B2
and B3 cases in his post on similar topics.
Basically, it is very wasteful and inneficient to always require that
decorated intervals propagate through an entire computation (particularly
since a decorated interval is likely never to be a power-of-two). Sometimes
the deocrations are useless, anyways, so only bare intervals are required.
Sometimes the intervals are useless (after an exception occurs), so only
decorations are required. Only in a few cases is both the interval and the
decoration always required. So only in those cases should an implementation
or algorithm suffer the overhead of decorated intervals. In other cases,
users, algorithms or hardware can employ forgetful operators and/or
operations on bare intervals/decorations to keep things efficient.
>
> Next:
>
> 3.1. This motion uniformly handles all arithmetic and
> nonarithmetic exceptions that are relevant for interval
> arithmetic and its applications. It eliminates the need for
> separate global sticky flags, and integrates non-intervals
> (NaI), without introducing any overhead for users who don't make
> use of exceptions.
>
> I grant that this is pretty clearly the intent of this motion.
> And I further grant that it is something we need to do. But
> I am a bit unclear on how the non-rationale portion of the
> motion accomplishes this.
>
> Specifically, just how are NaIs 'integrated' into other
> intervals 'without introducing any overhead'?
By the decorations, together with forgetful operators and operations on bare
intervals and/or bare decorations (as mentioned above).
>
> Are NaIs intended to live only within the decorations?
Yes, essentially the decoration becomes the "carrier" or "moral equivalent"
of the NaI information, particularly if a forgetful operator throws away the
interval portion of a decorated interval so all that remains is a bare
decoration.
>
> Or is there an interval portion of an NaI?
Only if it is a decorated interval. For a bare decoration, it is implied the
interval portion is the empty set.
>
> Is empty only a decoration or does it live in the interval
> as well?
Possibly both. A bare interval or the interval portion of a decorated
interval can be the empty set; possibly an isEmpty trit exists in the
decoration, as well. We can define whatever is required. The current motion
doesn't take a stand on this issue.
>
> Finally:
>
> 3.4. Useful candidates for decoration trits are:
> isValid possiblyValid notValid
> isStandard possiblyStandard notStandard
> isEmpty possiblyEmpty notEmpty
> isEntire possiblyEntire notEntire
> isBounded possiblyBounded notBounded
> isDefined possiblyDefined notDefined
> isContinuous possiblyContinuous notContinuous
> isTight possiblyTight notTight
> These fit exactly into 2 bytes if each trit is represented by
> two bits.
>
> This is an excellent set of decorations. It would seem to
> cover all we might need &, as you say, fits in 2 bytes.
>
> All the intended uses of these decorations (as well as good
> propogation rules) seem clear to me except for 'isValid' &
> its kin.
>
> What does this mean in the context of the other decorations?
I'm guessing it might be used to signal invalid construction or
uninitialized data. But perhpas as Hossam points out recently we may want or
need separate trits to distinguish the two.
>
> Thanks in advance for your clarifications of these questions.
>
> I think you're on the right path here.
>
In this motion, we try to fix only the general and conceptual framework.
Future motions can then begin to "drill down" into more specific levels of
detail and specification.
Sincerely,
Nate Hayes