Re: Bare decorations (was ...level 2 datums)
John Pryce wrote:
What I did not grasp before
---------------------------
<level3>
Bare decorations CAN be stored as single bytes, but we also give them
encodings in 16 bytes -- distinct from encodings of bare intervals. Thus
{intervals} union {decorations}
can be regarded as a single datatype, analogously to IEEE 754's
{F.P. numbers} union {NaN}
(in a given format, say binary64), forming a single set of floating point
datums. When viewed thus, the different bare decorations are, i.e. can be
defined to be, different kinds of NaI.
In particular, an *array* of 16-byte objects can hold a mix of intervals
and NaIs on which to do arithmetic -- but NOT general decorated intervals,
which need 17-byte objects.
Encoding the decoration values in NaN payload(s) looks promising, but may
need special hardware and/or revision to 754's NaN handling to be really
efficient.
</level3>
Yes.
Arithmetic
----------
Abstractly, arithmetic on a mix of bi's, bd's and di's is defined by
promoting each bi or bd to a di
With one important exception:
The only way to construct a decorated interval is from
-- a bare interval; or
-- a bare interval and a bare decoration.
Promotion is just a form of construction. Usually, promotion means the
construction is implicit. Hence, this means a bare decoration can never be
promoted to a decorated interval, since a decorated interval can never be
constructed only from a bare decoration.
If users wish to, they can override this behavior by explicitly constructing
a decorated interval. But this requires the user to explicitly provide both
a bare interval and a bare decoration from which the decorated interval will
be constructed.
The reason is so that a bare decoration will never be unintentionally lost
in a lengthy computation, i.e., to change this behavior the user must
explicitly choose to intervene for some reason and "reset" the decoration or
the computation.
then doing the operation on the resulting di's. This is Motion 8 §2.2-2.4,
but it needs rewriting:
(a) It doesn't cover a mix of operands, such as (bare interval) + (bare
decoration).
This is covered by 2.3 that says any operation involving a bare decoration
must always result in a bare decoration. In IEEE 754, this is analagous to
how any arithmetic operation involving a NaN must return a NaN, i.e.,
2 + NaN = NaN
and not something like
2 + NaN = 2
which would cause serious problems.
So in the example
(bare interval) + (bare decoration)
one could promote the bare interval to a decorated interval to obtain its
(optimistic) decoration. Then the infimum of the two decortations should be
returned as a result of the arithmetic operation.
(b) §2.3 must now say explicitly, I believe, that every bd is promoted by
giving it an empty interval part, i.e. it becomes (Empty, bd).
Section 2.3 was specifically re-written in the second version of the motion
to prevent this from happening. It is important that a bare decoration never
is promoted to anything, and that operations involving bare decorations
always return bare decorations.
As mentioned above, users can explicitly override this behavior if they wish
by constructing a decorated interval. But that requires the user to also
specify what is the bare interval portion of the decorated interval.
Its never safe to assume that the interval portion of a bare decoration is
the empty set.
(c) §2.4 seems to say that every bi is promoted by giving it the most
*pessimistic* possible decoration part. This is an error. It must be given
the most *optimistic* decoration.
In retrospect, I think thats probably true.
(d) Missing from the present Motion 8 description is the need for
"demotion" as the last stage of an operation. Otherwise if, say, I add two
of my vectors of 16-byte objects, I end up with a vector of 17-byte
objects. At level 1 & 2, can demotion be ignored? I don't find that
obvious; it is one of the consistency questions I mention below.
The idea is that users must always explicitly specify if they wish to keep
the bare interval or the bare decoration by using forgetful operators.
However, I don't see it would be a problem that an application or language
binding could specify some sort of demotion rule that says, e.g., the
decorated interval will be demoted to a bare interval if the decoration
portion of the decorated interval is "ok", otherwise it is demoted to a bare
decoration.
Example. Let xx,yy be bare intervals, and c,d be decorations. Let /-> mean
"promotes to" and \-> mean "demotes to". Then
x + y /-> (x,ok) + (y,ok) //optimistic, not pessimistic
= (x+y, ok)
\-> x+y
and
c + y /-> (Empty,c) + (y,ok)
= (Empty+y, max(c,ok)) //using Neumaier scheme
= (Empty, c)
\-> c
and
c + d becomes max(c,d) similarly.
If the operation is one that, unlike "+", can raise an exception, then in
this "16-byte mode" of arithmetic, the interval part of the result is
brutally discarded and the result is the decoration part, e.g.
sqrt([-1,4]) /-> sqrt(([-1,4],ok))
= ([0,2], possiblyEverywhereDefined) //Neumaier's dec=2
\-> possiblyEverywhereDefined
<<
Yes. I think these examples are on the right track.
Discussion
----------
We seem to have three kinds of interval arithmetic here:
- "Raw" 16-byte interval arithmetic, in which bare decorations (NaIs)
don't exist. An exception can occur locally to an operation, but these are
not propagated through a computation because there is nowhere to store
them. This is the underlying arithmetic in terms of which the other two
kinds are defined.
- The enhanced 16-byte arithmetic described above, in which when an
exception occurs, the interval part is discarded and the exception
propagates, "stickily", as a flavour of NaI.
- Full 17-byte decorated interval arithmetic.
Q1. Nate & Arnold. Am I reaching for the right end of the stick?
In my opinion, yes.
Just be careful to remember that a bare decoration can never be promoted to
a decorated interval. Users must always construct such a decorated interval
explicitly, if they wish.
Likewise, it is never safe to assume that a bare decoration is an empty set
in disguise, i.e., that somehow an empty set can be "extracted" or "promoted
out of" a bare decoration.
Otherwise I think you are on the right track.
Q3. I see no good reason why the different kinds of NaI that might be
found useful in applications should be in 1-1 correspondence with the
different decoration values used in whatever exception handling scheme we
finalise. Justification, anyone?
I don't fully understand the question.
All I can say in advance is that for branch-and-bound algorithms, one always
needs the full gamut of decorations to be be present in the payload of the
bare decoration (NaI). For example, the NaI should always have information
representing the state of the domain tetrit and the defined and contiuous
bit.
Finally, it is not obvious that this exception handling scheme is
self-consistent. I think it is now sufficiently well specified that one
could attempt to define what that means, and prove it.
Important to this notion of self-consistency is that bare decorations are
not promoted automatically to decorated intervals, and that bare decorations
are not empty sets in disguise.
Those are two pitfalls to stay away from.
Nate Hayes