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.)
> Property: X \subset Y ==> if (inf(X)==inf(Y)) then mid(X) <= mid(Y) &
> if (sup(X)==sup(Y)) then mid(X) >= mid(Y)
>
> Coercion: mid_F(X) = min(max(round2Nearest_F(mid(X)),-Fmax_F),Fmax_F)
> Property still holds so long as weak monotonicity
> holds for your arithmetic. That is true for 754
> & all other arithmetics extant (that I am aware of).
> But it was false for some sloppy arithmetics in the
> past. One must take care that the arithmetic is
> carried out in a fashion that does not overflow.
> This includes making sure that (-inf + +inf)/2 does
> not happen as an intermediate result. But both can
> be accomplished in more than one way. Property is
> trivially true for semi-infinite intervals in that
> all have the same midpoint which is to the correct
> "side" of all finite subsets. Further, the midpoint
> is an interior point so long as X HAS points in its
> interior that are representable in F. Otherwise,
> the midpoint might be an endpoint or even exterior
> to X altogether. Note that this is a problem with
> F not a problem with the definition of midpoint.
> Applying the Principle of Least Astonishment, it is
> my firm belief that a finite element of F should
> always be returned rather than a NaN on the grounds
> that "interiorness" is a derived rather than
> fundamental property of midpoint & is violated only
> when the user insists on it. That is, either by
> trying to split an unsplitable interval or by
> insisting on representing the midpoint in a
> floating-point type inadequate to the task.
> (Aside: this is mostly equivalent to Michel's
> midpoint.) The midpoint of Entire is arbitrary.
> Any finite value would do. But 0 is as good as
> any other & splits Entire right down the middle.
splits Entire right down the middle... *at Level 2*.
> 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?
> ----------
>
> 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.
> ----------
>
> 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).
> Property: X \subset Y ==> wid(X) <= wid(Y)
>
> Coercion: wid_F(X) = roundUp_F(wid(X))
> Property still holds if weak monotonicity holds
> in your arithmetic. Sufficiently wide finite
> intervals may have an infinite width returned
> if F has insufficient dynamic range to express
> that width. And care should be taken that the
> expressions +/-inf - +/-inf either never arise
> or are dealt with properly (easy to do). The
> "else if" clause is only needed for systems
> that choke on +inf - -inf & return a NaN (there
In the standard, this should be mentioned in a footnote, for instance.
> are still such systems around). After that,
> there is guaranteed to be one finite term in
> the "else" clause. At least at level 1. John
> also argues that wid(Empty) = -inf on much the
> same grounds as mag(Empty) = -inf. I prefer 0
> on Least Astonishment grounds but would have no
> great objection to the change.
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 }.
> ----------
>
> 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.
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.
> 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
which is better (more accurate) than Empty \subset [0,0].
--
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)