Re: (long) A new proposal for midpoint et al...
On 2012-02-21 08:51:43 -0800, Dan Zuras Intervals wrote:
> > Date: Tue, 21 Feb 2012 14:17:02 +0100
> > From: Vincent Lefevre <vincent@xxxxxxxxxx>
> > To: stds-1788@xxxxxxxxxxxxxxxxx
> > Subject: Re: (long) A new proposal for midpoint et al...
> >
> > On 2012-02-18 16:37:37 -0800, Dan Zuras Intervals wrote:
> > > Level 1: mid(X) = for non-empty X only: if (X==Entire) then 0
> > > else (inf(X) + sup(X))/2
> >
> > For X == Entire, 0 is a good choice at Level 2, in particular because
> > 0 is the only center of symmetry for most number formats and interval
> > types. I'm not sure whether the midpoint of Entire should be defined
> > at Level 1 because some properties are no longer true for Entire[*],
> > but since there isn't a Level 1 implementation, this probably doesn't
> > matter.
> >
> > [*] For instance, for any interval X different from Empty and Entire,
> > and any real number k, midpoint(X + k) = midpoint(X) + k. (This is
> > true for the semi-unbounded intervals, with the usual rules on the
> > extended real numbers.)
>
> As you mention below, I didn't say that 0 is the middle of
> Entire. I said 0 is as good a choice as any.
>
> For any Real number there are as many to the left of it as
> to the right. So, in a very real sense (forgive the pun)
> the Reals, although ordered, have no middle.
>
> The choice of 0 is arbitrary, no better nor worse than any
> other Real number. But far better than NaN.
It depends on its use. For interval splitting, it is a good choice.
But if the goal is to get an approximation to the midpoint (assuming
correct rounding and all variables occurring only once), then this
is not necessarily a good choice, just like (+inf) + (-inf) returns
NaN, not 0.
> > > Someday we may need to make a similar argument
> > > concerning midpoint(Empty). Can we choose 0?
> >
> > 0 doesn't make sense at Level 1. And Level 2, NaN should be available.
> > So, why not choosing NaN?
>
> My argument is going to be a philosophical one more than
> mathematical or numerical. (It will also be long. :-)
[...]
> Since our universe of discourse consists of contiguous
> sets of extended Real numbers, the empty set permits
> us to do something that we could not do in floating-
> point. Namely, not return an answer when there is no
> sensible answer. Empty says to the user, "There are
> no Real numbers that come out of this calculation."
> Like NaN in floating-point, our arithmetic is (for
> the most part) Empty preserving. So if one comes up,
> chances are the user will find out about it.
I don't understand what you mean by "the empty set permits us to
do something that we could not do in floating-point". Both NaN
and Empty are sensible answers. However IEEE's NaN has different
interpretations. For instance the NaN returned by (+inf) - (-inf)
is closer to Entire than to Empty.
> Now, this does not eliminate error analysis. After
> all, the user is probably going to want to know WHY
> there is no answer to the problem. But tracking
> that back to its source is no harder nor easier than
> before.
>
> In this context, there is no need for the interval
> equivalent of NaN: the NaI. Not at level 1. And,
> if we do our jobs right, not at level 2 either.
I partly disagree. While NaI isn't really necessary, I think that
it is a good idea to have it, because some operations still don't
make sense or are ambiguous. For instance,
text2interval("[1;2]")
If the comma is the separator (not the semi-colon), then this
doesn't make sense. It corresponds to text that means nothing,
not even the empty set like sqrt([-2,-1]). I think this is where
NaI can be useful: to tell the user that there is a problem
(e.g. a parsing error) beyond the mathematical meaning.
Similarly, converting an array (or array reference) or a structure
into an interval type (for languages where this is possible, e.g.
with dynamic typing) could result in NaI.
> But the table 4 functions are something of a problem.
> As they return floating-point results they throw us
> back into the problem of what to return when there
> is no sensible answer to return.
When there is no sensible answer to return, it should be like in
a floating-point operation: NaN.
> Now, we COULD punt & say to the programmer, "By
> executing a table 4 function you left the interval
> world of assured computing & re-entered the world
> of error-riddled floating-point. You have voided
> the warranty. You cannot go back to the interval
> world & count on anything to be correct. Anything
> bad that happens to you from now on is your own
> damn fault."
>
> As prejudicial as I make this sound, there is some
> merit to taking that position. This is what having
> mid(Empty) = NaN would mean to the user.
>
> But, we could also return a harmless but arbitrary
> answer. It might be that ANY numeric answer would
> do as well as any other. So, for example, splitting
> Entire "down the middle" & return 0 as its midpoint
> does no harm. And, since the intended purpose of
> finding a midpoint is (generally) to split an
> interval, splitting Entire into [-inf,0] & [0,+inf]
> is as good as splitting it anywhere else. And it
> is better than NaN.
The reason to want to split Entire is obvious. But is there any reason
to split Empty? I think the splitting process should end there. In
this case, getting the midpoint of Empty shouldn't ever occur (for
splitting); or this is a bug, in which case NaN is the best answer.
> Now, Vincent, I realize that you are not proposing
> that we do anything else than return mid(Entire)=0.
I was suggesting that it could be left undefined at Level 1 (though
I'm not sure that this is really useful and what relations between
Levels 1 and 2 intend to mean in particular cases like that). But I
agree that it can be useful at Level 2.
> But I make this (admittedly weak) argument in the
> hope that you might consider the possibility that
> ANY arbitrary answer for mid(Empty) might be better
> for the user than NaN.
>
> And better for us too. For if we are careful & see
> to it that there is no way of introducing NaNs into
> the structure of intervals, we free ourselves as well
> as the user from having to deal with all the problems
> they bring with them.
>
> So, my argument for a numeric mid(Empty) is
> mathematically even weaker than the one for Entire.
> But it is no more nor less arbitrary. And I believe
> that any arbitrary numeric answer is better, for us
> all, than NaN.
I don't see how an arbitrary value can be used in a useful manner.
And I don't think that returning a real value that is not a member
of the interval (even at Level 1) is a good idea.
Leaving mid(Empty) unspecified (possibly for some specification in
a future revision, based on new applications) would still be better
than an arbitrary value.
> > > Level 1: mag(X) = { least m>=0 such that m >= |x| for all x in X }
> > >
> > > Property: X \subset Y ==> mag(X) <= mag(Y)
> > >
> > > Coercion: mag_F(X) = roundUp_F(mag(X))
> > > Property still holds although intervals of sufficient
> > > finite magnitude may have +inf reported if F has
> > > insufficient dynamic range to express that magnitude.
> > > Other than Empty, [0,0] is the only interval with a
> > > 0 magnitude. All others are strictly positive. John
> > > has argued that the m>=0 should be removed which would
> > > render mag(Empty) = -inf. A case can be made for this
> > > but I, personally, prefer mag(Empty) = 0 on Least
> > > Astonishment grounds. Still, I would have no great
> > > objection to the change.
> >
> > 1. For sup_Rbar { |x| | x in xx }, that would be mag(Empty) = -oo.
> > 2. For sup_Rbar+ { |x| | x in xx }, that would be mag(Empty) = 0,
> > where Rbar+ = { x in Rbar | x >= 0 }.
> >
> > Since Rbar is the general reference set, I would say that (1) is
> > better, but I don't have a strong opinion on the subject.
>
> Well, since the user would be expecting a function called
> mag to be returning answers in Rbar+, I would vote for 0.
> But I also don't have a strong opinion on the subject.
However midpoint(asin[1,1]) could return a value outside the asin
range [-pi/2,pi/2]. So I wouldn't regard range behaviors as strong
arguments.
> > > ----------
> > >
> > > Level 1: wid(X) = if (X==Empty) then 0
> > > else if (X==Entire) then +inf
> > > else sup(X) - inf(X)
> >
> > Perhaps wid(Empty) could be undefined. 0 doesn't make much sense,
> > and note that sup(X) - inf(X) = -oo for X = Empty. So, wid(Empty)
> > could also be -oo (better than 0, IMHO).
>
> Since both points & Empty have zero measure among
> the Reals, 0 make as much sense to me as anything.
If what is considered is the measure, then I would rename "width"
to "measure".
> > See my opinion above. But if you choose 0, you should use the
> > following definition:
> >
> > wid(X) = sup_Rbar+ { a - b | a in X, b in X }.
>
> How is that different from sup(X) - inf(X)?
sup and inf are over Rbar. If you assume that wid(X) should return a
value in Rbar+ (the nonnegative real numbers), then the sup should be
taken over Rbar+.
> > > ----------
> > >
> > > Level 1: rad(X) = if (X==Empty) then 0
> > > else mag(X - mid(X))
> >
> > I would say that the definition should be equivalent to wid(X)/2
> > at Level 1, for Empty in particular.
>
> Alas, Nate & I tried something along these lines &
> it didn't work. See the discussion of equation (22)
> either below or in our old proposal.
I meant at Level 1 (since I was quoting a Level 1 definition).
But now, after some thoughts, if wid and rad serve difference
purpose (rad being linked to the midpoint), there's no reason
why they should be equivalent after all, even at Level 1.
> > Your definition is invalid for semi-unbounded intervals because
> > X - mid(X) is undefined for such intervals at Level 1. But it
> > seems to be OK at Level 2.
>
> That is so. It is part of why I describe the coercion
> to level 2 as "a bit tricky".
But I think that more could be said at Level 1 (e.g. explicitly
saying unspecified for such cases).
> > > Property: X \subset Y ==> rad(X) <= rad(Y)
> > >
> > > Coercion: rad_F(X) = if (X==Empty) then 0
> > > else mag_F(X - mid_F(X))
> > > This one is a bit tricky. Note that the coercion
> > > is subtly different from all the others & is needed
> > > for both weak monotonicity & (22) to hold. Given
> > > that, property still holds if (1) mid_F returns the
> > > nearest representable finite number in F rather than
> > > a NaN & (2) weak monononicity holds in your arithmetic.
> > > Some finite intervals will return an infinite result
> > > if F is unable to represent the finite value. Care
> > > should be taken that +/-inf - +/-inf either never
> > > arises or is dealt with properly (easy to do).
> > > Further, Nate's (22)
> > >
> > > X \subset [mid_F(X) - rad_F(X), mid_F(X) + rad_F(X)]
> > >
> > > holds so long as not both mid_F(X) & rad_F(X) are
> > > infinite. It would also hold for Empty if mid(Empty)
> > > is not a NaN. But chances are, that's too much to
> > > ask for. Equation (22) is going to be needed if we
> > > want to use X -> <mid_F(X),rad_F(X)> to preserve
> > > containment on conversion to mid-rad. We already
> > > have X -> [inf_F(X),sup_F(X)] for inf-sups. We will
> > > need both. Note that we can have rad_F(X) > wid_F(X)/2
> > > in some cases. Indeed, we can have rad_F(X) = wid_F(X).
> > > I could make a good mathematical argument for why this
> > > is so but only another mathematician would fall for it.
> > > In the end, it is because wid() & rad() are defined
> > > very differently. For the moment, we cannot have
> > > rad(X) > wid(X) but if John's arguments about Empty
> > > hold sway we will have rad(Empty)=0 > wid(Empty)=-inf.
> >
> > If wid(Empty) = -oo, then one should define rad(Empty) = -oo.
> >
> > > Perhaps an argument against it. Perhaps not. Note
> > > that we cannot have rad(Empty)=-inf & still preserve
> > > containment on conversion to mid-rad.
> >
> > I don't understand. Empty is a subset of everything. So,
> > the containment property will necessarily be satisfied.
> > In particular, for X == Empty,
> >
> > X \subset [mid_F(X) - rad_F(X), mid_F(X) + rad_F(X)]
> >
> > would give:
> >
> > Empty \subset [+oo,-oo] = Empty
>
> Actually, your line of reasoning would lead to
>
> Empty \subset [NaN - -inf, NaN + -inf] = [NaN,NaN]
>
> Thus the special cases involving Empty.
At Level 1, there is no NaN. At Level 2, [NaN,NaN] (meaning
nums2interval(NaN,NaN)) is Empty. So, rad(Empty)=-inf is OK.
Anyway, if mid(Empty) is NaN/undefined/unspecified, then Empty is
a particular case whatever the choice of rad(Empty). If mid(Empty)
is a real value, then for X = Empty and rad(Empty)=-inf, one has:
[mid_F(X) - rad_F(X), mid_F(X) + rad_F(X)] = [+oo,-oo] = Empty
and the containment on conversion to mid-rad will be preserved.
IMHO, rad(X) < 0 is a way to represent Empty in a mid-rad format.
> > which is better (more accurate) than Empty \subset [0,0].
>
> Well, Empty \subset [0,0] is at least true.
>
> Arbitrary but true.
But Empty is a more accurate result. In an inf-sup -> mid-rad
conversion, Empty should be converted to Empty. And IMHO, the
standard should require that Empty and associated decorations
be preserved in interval type conversions (in particular, NaI
will be preserved).
--
Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)