Sorry, my example in error Re: Tetrits and "stickiness"
All,
Sorry, the example I gave was in error, since g actually does have a
fixed point in [1,3], namely (3 + \sqrt{5})/2. Try g(x) = 0.5\sqrt{x-1} + 0.5\sqrt{x}
and \x = [0,1]. Then, g(\x) = [0,0] + [0,0.5] = [0,0.5], and the hypotheses of
the Brouwer fixed point theorem would be satisfied, but g has no fixed point
in the portion of the interval within the domain. Did I get it right this time?
Baker
===========================
Dan et al,
The implications of this will require some additional thought. In particular, how the tetrits will actually
be used in computations should be reviewed carefully. My guess is that, if an argument is not totally in
the domain of part of the expression, we need to say the argument is not wholly within the domain of
the entire expression. This would be important to know in the case of computational fixed point
theorems. To remind people, an example is
g(x) = \sqrt{x}+1, and take \x = [-2,4]
Then, g([-2,4] = {[1,3],{domainIn,domainOut}}, but the Brouwer fixed point theorem
would say there is an x in [1,3]\subset [-2,4] with g(x)=x, except for the DomainOut tetrit.
From this point of view, the sticky part is most important. (Note that I have not distinguished
sticky and non-sticky here.)
The main potential use of the non-sticky part would be to find out where in the expression
(through a user check of the tetrit, say) the domain condition is violated.
Do we need both the sticky part and the non-sticky part? If we don't, can we simplify
this even more? I'd be interested in Arnold's and John's opinions, among others. Otherwise, I don't
see adding an additional bit a problem, but what do hardware people think? Perhaps we even have
an extra bit of "Lagniappe" (as we say here in South Louisiana), since perhaps we could even carry a fourth
bit free of charge to make it an even half-byte :-)
Baker
On 4/14/2010 8:41 PM, Dan Zuras Intervals wrote:
.
.
.
Nate,
First let me say this is very clever& I like anything
that might make the decorations more useful.
It is a bit hard to follow on first reading but that's
no big deal: We just define the 4 values to mean what
we want them to mean& how we compute them is mostly
a circuits issue.
So, with that in mind, I'd say that any rearrangement
of the 4 bit patterns is mostly as good as any other&
yours is better than mine for this purpose.
However,& you knew there was a however coming (:-), it
is not the sqrt() that issues the final decoration but
the next operation. That is, the domain error was not a
domain error of the final operation but a domain error of
the sqrt(). As you are assuming it was a dyadic operation,
let's assume it was an add just for argument's sake.
So, the expression is:
xx = [1,2];
yy = [-2,1];
rr = sqrt(xx) + sqrt(yy);
and the question becomes what is the decoration on rr&
what does it mean. If we propogate the decorations on the
sqrts in the manner you suggest we would get (1,0) meaning
that the result of the add is something like:
rr = {[1,1+sqrt(2)],{domainIn,domainOut}}
as well as any other decorations that don't concern us for
now.
Now, I will assume that what you meant to say in the above
propagation rule is that the propagated decoration is the
infimum of operands TOGETHER with the decoration for this
operation. (Correct me if I'm wrong here.) I also assume
that the proper domain of the add is [entire]. (That IS
right, isn't it?)
So, the user gets rr, looks at the decoration& wonders:
Is that OK or is there something wrong with my calculation?
The user is kind of lucky in this case in that the domainOut
cannot have come from the add. The domainIn could have been
inserted by the add but your assignment of decoration values
also has the merit of returning (0,0) had either input been
(0,1) or (0,0) (an empty interval operand). So the user can
deduce that the input operands must have been either (1,1)&
(1,0) or both (1,0). The obvious thing is to suspect one or
the other sqrt& trace back from there.
All in all, not bad.
Still, the decorations as we have been discussing them have
a flavor of the 'exceptional' to them not unlike the flags
in 754. Now, I do not mean by that that we should consider
things like the 754 flags. They have been more pain than
they are worth in the last 3 decades, IMHO.
But I AM suggesting that the thing about decorations we want
to retain as sticky is that which concerns us, namely the
information about anything exceptional that happened for this
operation or in the past.
In the case of the 'domain' decoration that would mean keeping
information any past domain errors around for future diagnostic
use.
Now, my first thought is to expand the tetrits to 3 bits (an
octit, perhaps? :-) with the first two bits giving information
about the status of this last operation only& the third bit
collecting past exceptional behavior as sticky.
In your example that would look something like:
xx = {[1,2],{}}; /* just to start clean */
yy = {[-2,1],{}}; /* just to start clean */
zz = sqrt(xx) = {[1,sqrt(2)],{domainIn}};
ww = sqrt(yy) = {[0,1],{domainIn,domainOut}};
rr = zz + ww = {1,1+sqrt(2)],{domainIn,wasDomainOut}};
In this case there is not propagation rule for the first two
bits as they are a function of the current operation only.
The sticky bit (wasDomainOut, or whatever) would be the 'or'
of all of the input domainOut's in the input sticky's. That
way the fact the the domain error was from some previous
operation does not depend on the luck of the operation& the
other bits are as simple as the interval calculations themselves.
In this case, the status can just be read off:
domainIn = true means that the add could handle both
operands,
domainOut = false means that nothing was exceptional
to the add,
wasDomainOut = true means that some previous operation
had operands exceptional to THAT operation not
the add.
Still, this involves more bits.
Yours does not.
I'm not sure which is best.
Mine has K.I.S.S. on its side.
Yours has fewer bits& almost the same information.
What does everyone else think?
Got to go now. The rest of my life has come calling. :-)
Dan