Re: Constructors & decorations
> Subject: Re: Constructors & decorations
> From: John Pryce <j.d.pryce@xxxxxxxxxxxx>
> Date: Tue, 23 Feb 2010 08:58:05 +0000
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
Folks,
I will try to give brief but detailed responses to
John's comments here.
I will fail on the brief part. :-)
I would normally edit this down a bit to make it more
readable for everyone but as John & I both chose to
define nomenclature in our arguments, its hard to
eliminate that & still have the arguments make sense.
The best I can say is that, in summary, we basically
agree on the nature of decorations & are arguing the
nature of the wings on the angels dancing on the head
of our pin here.
Unless that interests you, you can safely ignore this
note.
John,
If we go further, perhaps we can take this offline
until we come to some understanding before we bug
everyone else with this.
>
> Dan & P1788
>
> I will try to get to grips with Dan's specific examples
> about decorations on 9 Feb.
>
> For brevity I write V, D, C, B for the Valid, Defined,
> Continuous and Bounded attributes and + 0 - for the
> values "is", "possibly", "not". Then e.g., D0 means the
> same as possiblyDefined. And e.g.,
> ([1,2],V+,D0)
> means interval [1,2] with its V attribute set to +, its
> D attribute set to 0, and not saying anything about its
> C and B attributes.
>
> Response interspersed below.
>
> On 9 Feb 2010, at 23:44, Dan Zuras Intervals wrote:
>
> >> On 9 Feb 2010 22:24:56 +0000, John Pryce wrote
> >> Dan
> >> On 9 Feb 2010, at 21:54, Dan Zuras Intervals wrote:
> >>> This may be a bit of a topic drift but what is the difference
> >>> between Valid & Defined?
> >> Ah. There are 3 conceptually different groups.
> >>
> >> isValid: The result of a valid constructor call, or of an operation =
> >> whose inputs were isValid. So recursively, an interval value that makes =
> >> sense, "not NaI".
> >>
> >> isDefined, isContinuous]: Only make sense in the context of evaluating =
> >> the interval version yy=ff(xx1, ..., xxn) of a point function y=f(x1, =
> >> ..., xn). If the original xx's are all isDefined [resp. isContinuous], =
> >> and the resulting yy is isDefined [resp. isContinuous] then one has =
> >> proved f is defined [resp. continuous] at each point of the input box =
> >> (xx1 cross ... cross xxn) in R^n. (cross = cartesian product).
> >>
> >> isBounded: Unlike the others, not about history. Just says that xx is =
> >> mathematically bounded even though a bound might have overflowed to oo.
> > ...
> > John,
> >
> > While all of this makes sense to me I'm not sure it answers
> > my questions. Let me try some examples:
> >
> > Let f = sqrt(x^2 - 1)
> >
> > So, if I understand your argument correctly, the evaluation
> > of yy = ff(xx) is,
> >
> > (1) Valid (Bounded) iff the input is Valid (Bounded),
> Yes.
> > (2) Defined (Continuous) for all Defined (Continuous) inputs
> > except for xx such that xx \intersect (-1,1) is non-empty,
> Yes again. I make it that if xx is D+ then yy is
> D+ if xx \intersect (-1,1) is empty,
> D- if xx \subseteq (-1,1),
> D0 otherwise.
> The situation for C is the same, in this example.
Ah, in this case your interpretation of the uncertainty
associated with the word 'possibly' is in the fact that
the result in the D0 case was evaluated on an interval
that containes SOME numbers that are defined & SOME
numbers that are not. Therefore, we say the resulting
interval is 'possiblyDefined' in that, for any given
point in the input interval, it might or might not be
defined depending on which point you are looking at.
I'm OK with this interpretation of 'possibly' in this
case.
>
> > Also ff could return possiblyBounded in the case where the
> > input is Bounded but the intermediate expression x^2 overflows.
> Ah, no! The whole point of Bounded, as I understand it, is to
> remember a _mathematical_ truth that floating-point may have
> forgotten. Suppose BIG is such that BIG^2 overflows. Then
> yy=ff([1,BIG]) is evaluated as sqrt([1,BIG]^2-1) =
> sqrt([1,oo]-1) = sqrt([0,oo]) = [0,oo]
> but the initial [1,BIG] is B+, and this is preserved all
> through, hence yy is B+.
So, if we break down the evaluation of ff into its
component steps, you would have us propagate B as:
xx = {[1,BIG],B+}
uu = {[1,BIG],B+}^2 = {[1,oo],B+}
vv = {[1,oo],B+} - 1 = {[0,oo],B+}
yy = sqrt({[0,oo],B+}) = {[0,oo],B+}
Again, I am OK with this.
It allows us to distinguish intervals with infinite
endpoints arrived at via overflow from those arrived
at via the evaluation of a function that returned an
infinity for some point in the input interval. Those
would be B-, of course.
>
> This brings me to another point. When if ever should we use the
> B0 value? Suppose xx is an interval containing 0. Is yy=1/xx
> notBounded, or is it possiblyBounded? We believe that xx encloses
> some "true set of values" ss, and we don't know ss contains 0.
> So why should we assert yy is definitely B- ? It seems B0 is
> correct. Someone help me with semantics here.
>
> Same with tan(xx) where xx contains \pi/2, say.
These are the propagation issues I'm wrestling with.
I believe that the evaluation of a function with the
property that f(oo) = oo should propagate
'possiblyBounded' if the input is 'possiblyBounded'.
But that just recursively begs the question.
The most obvious example is the creation of an
interval with a constructor along the lines of
xx = intervalConstruct(1,oo,B0).
This uncertainty derives from the original sin that
the user was uncertain whether or not the input was
infinite but knew no upper bound. I think this is
contrived, though.
You mention the example of tan(xx) on an input of,
say, xx = [0,\pi/2+eps] where, \pi/2+eps is the
smallest representable number larger than \pi/2.
In this case the mathematical evaluation becomes
yy = tan(xx) = [0,oo] \union [-oo,-1/eps]
where the second interval represents the amount the
tangent was evaluated just past its first pole.
Unless some form of the tangent along the lines of
Motion 11 is used, we probably have to return Entire
in this case.
The fact that xx may have been created slightly wider
than was physically possible for the problem at hand
is irrelevant. That is what was asked of the tangent
function & that should be returned.
Should we decorate it with B0 or B-? I will argue
B- in this case on the grounds that any uncertainty
due to roundoff error was not tracked in any way
that might lead us to consider otherwise. In other
words, it may be uncertain whether or not the physical
problem can pass through this pole but it IS certain
that the computed interval did so.
I can think of no example off the top of my head that
is less contrived than B0 caused because someone SAID
it was B0.
All that having been said, I don't think it will cause
us any difficulty with the propagation rules.
>
> Dan continued:
> > Now let f = 1/sqrt(x^2 - 1)
> >
> > I believe we have,
> >
> > (1) Valid iff the input is Valid,
> > (2) Defined for all Defined inputs except for xx such that
> > xx \intersect (-1,1) is non-empty,
> > (3) Bounded (Continuous) for all inputs except for xx such
> > that xx \intersect [-1,1] is non-empty,
> I agree with you on all these, I think.
>
> > Note that this last is [-1,1] rather than (-1,1).
> Yes
> > And that overflow cannot happen in this case.
>
> Why not? With my BIG as above, let xx=[2,BIG], say. Doesn't
> floating point compute
> ff(xx) = ... overflow ... = 1/[sqrt(3),oo] = [0,1/sqrt(3)]
> (upper bounded rounded up of course)?
Ah, no. Well, an overflow in the floating-point
evaluation of the intermediate expression can happen
just as before. But, as we have dealt with that case
unambiguously, there is no further overflow possible
in the divide. There is an exact evaluation of 1/0
which happens in this case but that means B- not B0.
To extend the example above by one more step we have:
xx = {[1,BIG],B+}
uu = {[1,BIG],B+}^2 = {[1,oo],B+}
vv = {[1,oo],B+} - 1 = {[0,oo],B+}
ww = sqrt({[0,oo],B+}) = {[0,oo],B+}
yy = 1/{[0,oo],B+} = {[0,oo],B-}
All quite certain. Nothing possibly about any of it.
I only mentioned that the overflow cannot happen because,
to use a simpler example, the expression 1/(x - 1) may
evaluate to oo for x = 1 but there is no eps small enough
so that 1/eps overflows for x = 1 + eps.
In any non-pathalogical floating-point system the exponent
range far exceeds the precision. Thus the difference
between two representable numbers near the middle of the
range (like (1 + eps) - 1) is proportional to the precision
so the reciprocal (1/eps) may be large but it is far FAR
smaller than the range available.
No overflow.
>
> > Do I have that correct?
> >
> > Now, can you give me an example of an interval that is Defined
> > but not Valid?
>
> I believe not. I think the intention of Motion 8 is that once
> an interval is set notValid, _all_ its other attributes become
> meaningless. It has fallen into a black hole. So a V- interval
> is essentially the same as NaI. It follows that all query-functions
> on it should give results of maximum meaninglessness:
> - Its other decorations should be D0 C0 B0.
> - Its lower & upper bounds, midpoint, radius etc., should all return NaN.
So it seems that you are reserving the interpretation
of 'Valid' things to those things which are imported
into intervals from other arithmetics. Constructors,
converters, & the like.
Does that not seem like a particularly narrow use for
a decoration? Would not 'Defined' do as well?
I say this because decoration bits might end up being
expensive things some day. If we are successful &
intervals find their way into hardware, decoration bits
will become state bits. They will have interlocks &
busses devoted to them. They will be saved on context
switch. They will become involved in issues of
parallelism & cache coherency. We should make sure
they are useful.
On the one hand, I will argue that parsimony suggests
that overloading constructor issues into the 'Defined'
decoration might be desired.
On the other hand, before we are done I suspect we may
need decorations beyond 'Defined', 'Continuous', &
'Bounded'. For example, 'Standard' (versus
non-standard). As well as 'Accurate'. And possibly
'Empty'.
While these things are expensive to future generations
of hardware guys, failing to account for some important
property carries its own expense to future generations
of software guys.
>
> > As for Bounded, it seems to me that any result interval with
> > an infinite endpoint is notBounded only if it were evaluated
> > over a pole of some kind. Otherwise, in the overflow case,
> > I think possiblyBounded is the best answer.
>
> Yes. And, because we only "do" outer enclosures, not inner ones,
> we can never (except for cases like 1/[0,0]) be sure that we
> _have_ evaluated over a pole; see above.
>
> > I think I would like to explore these issues further in a
> > discussion of propagation rules.
>
> Thanks for raising these issues Dan. I also would like to look
> at them in more detail. If the semantics of decorations turn out
> to be too complicated to explain to the ordinary user, we need
> to re-think.
>
> Regards
>
> John
I think the semantics of decorations can be simplified
to the same 3-state state machine for all decorations
if they are named properly. Only the sense of the name
(the usual thing versus the unusual thing) needs to be
pinned down. Then the state machine will work.
But I will save my arguments for a future note.
Motion 11 is on the table today. We should devote our
time to that.
Also, the rest of my life has intervened to prevent me
from writing up my thoughts on this matter so I'm not
ready yet. :-)
I'm sure there are many of you who know how that feels.
Until then,
Dan