Decorations and Motion 22
Nate Hayes wrote: [Re: Discussion paper: what are the level 2 datums?]
Arnold Neumaier wrote:
Nate Hayes wrote:
Arnold Neumaier wrote:
Nate Hayes wrote:
Arnold Neumaier wrote:
Anyway, one must be able to conclude from the decoration whether
or not
an interval is valid, and one needs at least operations extracting
the four trits v d c b from a tetrit representation.
Agreed.
Any interval with a "domain" decoration (F,F) is invalid. This is
also the "worst" state of a tetrit, i.e., by the propagation rules
of tetrits it is impossible that (F,F) could ever be "absorbed",
"lost", or "changed" into another state that is either better or
worse. So it is the perfect state to represent invalid
constructions and/or uninitialized interval variables.
The new domain tetrit provides the four states:
priority tetrit trit meaing
3 (T,F) + "is defined"
2 (T,T) 0 "possibly defined"
1 (F,T) - "is undefined"
0 (F,F) "nowhere defined, nowhere undefined"
The first three states and thier meaning are the same as the old
trits. But with trits, there was not an equivalent of the (F,F)
state, which essentially makes the distinction of "v" in the above
example.
I'm fairly certain the only decorations IEEE 1788 needs are
"defined", "continuous", and "bounded".
We need all four. But we can dispense with the ohers.
If we were still using trits, then "v" might be needed. But since
we are now using tetrits I believe "v" is not necessary.
Does the interpretational difference matter when there are only 10
different combinations that are useful? With tetrits it shoudn't
be significantly more.
Tetrits simplify and reduce the number of "unusable" combinations.
In place of 3^4=81 we have now 4^3=64 combinations.
A slight reduction, but still far off the 10 or so useful ones.
Right. But keep in mind, too, that "defined and continous" will only
be a single bit (and not a tetrit) if Motion 22 passes. So between
the "domain" and "defined and continous" decorations that is only
2*4=8 combinations, of which 3 would be useless. However, there is no
way to represent 5 states in fewer than 3 bits of information, anyways.
So one can probably map the trit formulation and the tetrit
formulation equivalently to 10 (or 16) abstract decoration objects
that are just organized differently by the two formulations.
Yes.
It would be nice to have an explicit such correspondence.
So how do the 5 or 8 combinations of Motion 22 and the 10 trit
combinations
v d c b | #cases
- 0 0 0 | 1
+ - 0 0 | 1
+ 0 0 0- | 2
+ + +0 +0- | 6
v=valid, d=-defined, c=continuous, b=bounded
+ (True), - (False), and 0 (no claim),
correspond to each other?
Let me just concentrate on v, d, and c for now.
Below are the states represented in terms of the "domain" tetrit (Motion
18) and a "defined and continuous" bit (Motion 22 + Amendment), as well
as thier v, d, and c equivalents as you describe them above:
domain d&c v d c meaning
(T,F) T + + + "is defined and continuous"
(T,T) T + 0 + useless
(F,T) T + - + useless
(F,F) T - 0 + useless
(T,F) F + + 0 "is defined"
(T,T) F + 0 0 "possibly defined"
(F,T) F + - 0 "is undefined"
(F,F) F - 0 0 "nowhere defined, nowhere undefined"
The table shows that IEEE 1788 only needs the "domain" tetrit (as
defined in Motion 18) and a "defined and continuous" bit (as defined in
Motion 22 + Amendment) to efficiently encode all of the desired states
otherwise represented by the v, d and c trits. Furthermore, this
encoding only requires a total of 8 combinations, of which only 3 are
useless. So it is the most storage-efficient method, since it is not
possible to represent the 5 valid states in fewer than 3 bits, anyways.
Thanks. This almost matches what I had mentioned in my first mail
in this thread:
<begin quote>
(Actually, I do not really care how the decorations are defined in
the standard, as long as the definition is simple and unambiguous,
and lets one correctly recognize the cases v=d=c=b=+ needed for
existence theorems and d=-0+ if v=+, needed for set covering.
So from my perspective, one would only need to distinguish the five
cases -000, +-00, +000, ++00, ++++, and widen the other cases into
the appropriate relaxation. But any refinement of these would be ok.)
<end quote>
If the d&c bit is replaced by a d&c&b bit, the match is perfect, with
domain = (d1,d2) and d&c&b = d3:
dec d1 d2 d3 v d c b
0 T F T + + + + (safe =
(everywhere defined, continuous, and bounded)
1 T F F + + 0 0 (defined)
2 T T F + 0 0 0 (possibly defined)
3 F T F + - 0 0 (nowhere defined)
4 F F F - 0 0 0 (not valid)
Remarkably, the encoding of these decorations by a single uint3 gives
simple tests for those decoration properties that are important for
algorithmic tests:
isValid dec<4 d1||d2||d3 v
possiblyNonempty dec<3 d1 v & d>=0
everywhereDefined dec<2 d1 && ~d2 v & d
isSafe dec<1 d3 v & d & b & c
notValid dec>3
isEmpty dec>2
possiblyUndefined dec>1
notSafe dec>0
Thus the encoding into d1-d3 or v d b c or any other scheme can be left
to the implementor, whereas the uint3 representation should be required
as an interchange format.
The resulting scheme is simple, easy to understand, easy to encode, and
serves all practical purposes that are important for optimiztion,
equation solving, and ODEs. (One extra sign bit would easily fit in by
using int4 in place of uint3, should someone really need more.)
If someone likes this scheme, here is a proposed wording for a possible
motion:
========================================================================
It is proposed that precisely the following five decorations shall be
available:
dec = 0: safe = everywhere defined, continuous, and bounded)
dec = 1: everywhere defined
dec = 2: possibly everywhere defined
dec = 3: nowhere defined
dec = 4: not valid
In all interval exchange formats, a decoration is encoded by an
unsigned integer dec taking one of the values 0, 1, 2, 3, or 4.
The encoding in a datatype is left to the implementor.
The following unary predicates shall be provided for bare decorations
and for decorated intervals of any supported idatatype:
isValid dec<4
possiblyNonempty dec<3
everywhereDefined dec<2
isSafe dec<1
notValid dec>3
isEmpty dec>2
possiblyUndefined dec>1
notSafe dec>0
======================================================================
Since this is not fully compatible with Motion 22, it would preferably
be decided simultaneously with the latter.
Arnold Neumaier
PS.
Michel Hack wrote [Re: Motion P1788/M00018.01:TritsToTetrits: NO]
> What I am missing in the Trits-to-Tetrits paper is a statement that
> covers such situations, and that permits a case-based implementation
> of functions such as min(x,1/x**2) that avoids reporting a domain
> error.
This would have to be done by a compiler-level analysis of the
expression, since there can be no general rule of the kind you hope for.
For in the similar example min(x,-1/x**2), the domain error is
appropriate.
But if the compiler can prove that min(x,1/x**2) is equivalent to
x if x<=1,
1/x^2 otherwise,
it can of course implement the expression as
(x intersect [-inf,1]) union 1/(x intersect [1,inf])^2).