Re: Bare decorations (was ...level 2 datums)
Nate, Arnold, P1788
OK, I think I start to get it. Despite reading Motion 8 many times, I have mistaken one of its main purposes since day one. Bear with my attempt to explain in my own words. My brain requires examples of how what we are specifying may be efficiently implemented, hence the mixture of level 3 amongst the level 1 & 2.
Vladik, I hope this looks useful to you.
<level3>
To be specific I assume
- A bare interval needs 16 bytes to store it.
- A decoration fits into the smallest sensible storage unit,
i.e. 1 byte.
The decoration can be Arnold's recent "pentit" 0 to 4 scheme,
or any of the others we've considered. I'll call its most
optimistic value "ok": that's 0 for Neumaier pentits, 3 for
the integer encoding of Hayes tetrits.
- An array means an array of actual values, not an array of
references to values or similar fancy stuff.
</level3>
Motion 8 defines abstract objects called bare intervals (bi), bare decorations (bd) and decorated intervals (di). It assumes a decoration is a list of trits, which we've moved away from, so needs interpreting somewhat freely in places. In particular "least informative" should be read as "worst", which translates to "minimum" for Hayes' scheme, "maximum" for Neumaier's.
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>
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, 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).
(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).
(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.
[The other error, I believe, is that the hypothesised "emp" decoration at end of §3.2 doesn't now exist and can be replaced by "ok".]
(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.
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
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?
Q2. COMPILER & HARDWARE PEOPLE out there. We are scared of 17-byte arithmetic:
Corliss, 5 Sep 09:
"OF COURSE a standard for class DecoratedInterval would
violate KISS BIG TIME, and it would risk losing a speed
contest with a glacier :-) "
Pryce, 8 Sep 09:
"Is P1788 going to ...offer the world an IEEE standard
data-type of width 17 bytes? We should be a laughing stock."
Hayes, 17 Oct 2010:
"I would not use a 17-byte datatype in my software or products."
But it has the great advantage, for certain applications, of giving an enclosure for the range of a function f AND the information that f may not be everywhere defined on the input box.
Should we be scared in perpetuity? E.g. is a vector of a million objects made of (16 byte interval, 1 byte decoration) always going to be wastefully stored and/or slowly accessed? I seem to remember one of you saying that's not so.
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?
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.
Regards
John Pryce