Re: Table 4 proposal version 0.4, less midpoint...
On 2012-04-25 11:12:25 -0700, Dan Zuras Intervals wrote:
> () Both the generic (result floating-point type the same
> as that which underlies the operand) & formatOf functions
> are explicitly defined. The properties still hold no
> matter what the result format.
Note that with implicit interval types, you do not have a number
format that underlies the operand. So, you only have formatOf
functions. See Motion 33.
> ----------
>
> Level 1: inf(X) = { greatest i such that i <= x for all x in X }
You should say: greatest i in Rbar such that...
> Note that inf(Empty) = +infinity. This is important.
>
> Property: X \subset Y ==> inf(X) >= inf(Y)
>
> Coercion: inf_F(X) = roundDown_F(inf(X))
IMHO you should give the resulting Level 2 property:
inf_F(X) <= inf(X), i.e. inf_F(X) <= x for all x in X.
> That the level 1 property still holds follows from weak
> monotonicity on the mapping of the Reals to the elements of F.
Note that correct rounding is currently not mandatory in Motion 33
on the number formats (it is just recommended), except for IEEE 754
associated formats. The reason is that for instance, inf(X) may be
an advanced function of X, e.g. involving elementary functions. This
means that the Level 1 property X \subset Y ==> inf(X) >= inf(Y) might
not be satisfied at Level 2 (the implementation will decide what the
best choice is); for something that is neither part of the IEEE 754
world nor entirely in the interval world, I don't see this as a real
problem: users who want strong properties on the non-interval side
should go for a 754-conforming P1788 implementation.
> That we have inf(Empty) = +infinity is required as Empty is a
> subset of all sets. Any semi-infinite on the -infinity side &
> inf(Entire) = -infinity. Also, inf_F(X) may report -infinity
> if F has insufficient dynamic range to express an otherwise
> finite inf(X). All other non-empty sets have finite inf's.
> So in any given F it would be sufficient if inf_F(Empty) >=
> Fmax_F. But +infinity is the only correct level 1 answer.
Yes.
> ----------
>
> Level 1: sup(X) = { least s such that s >= x for all x in X }
Like above: least s in Rbar such that...
> Thus, sup(Empty) = -infinity.
>
> Property: X \subset Y ==> sup(X) <= sup(Y)
>
> Coercion: sup_F(X) = roundUp_F(sup(X))
Like above: sup_F(X) >= sup(X), i.e. sup_F(X) >= x for all x in X.
> Property still holds due to weak monotonicity. And sup(Empty)
> = -infinity is required at level 1 although sup_F(Empty) <= -Fmax_F
> is sufficient for any given F. Semi-infinites on the +infinity
> side & sup(Entire) = +infinity. Also, sup_F(X) may report
> +infinity if F has insufficient range to express inf(X). All
> other non-emptys are finite.
>
> ----------
>
> Note: mag takes arguments in IRbar & returns results in Rbar+.
>
> Level 1: mag(X) = { least m>=0 such that m >= |x| for all x in X }
Like above: least m in Rbar+ such that...
> Property: X \subset Y ==> mag(X) <= mag(Y)
>
> Coercion: mag_F(X) = roundUp_F(mag(X))
Like above: mag_F(X) >= mag(X), i.e. mag_F(X) >= |x| for all x in X.
> Property still holds although intervals of sufficient finite
> magnitude may have +infinity 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. Both John & Vincent have argued that the m>=0 should
> be removed which would render mag(Empty) = -infinity. A case can
> be made for this but I, personally, prefer mag(Empty) = 0 on Least
> Astonishment grounds. It was Vincent who provided me with the
> level 1 definition that accomplishes this goal.
"Least Astonishment grounds" is here subjective. For instead, other
definitions (inf, sup) use greatest i / least s in Rbar, so that
one may want to use Rbar here too. Now, is there a standard math
definition for the magnitude of an interval (or more generally a
set)? And what is the best practical choice (e.g. for algorithms)?
> ----------
>
> Note: mig takes arguments in IRbar & returns results in R+.
results in Rbar+?
> Level 1: mig(X) = { greatest Real m such that m <= |x| for all x in X }
Why real and not in Rbar or Rbar+ (for Empty)? Anyway, as is,
this definition doesn't make sense for Empty because R doesn't
have a greatest element.
> Property: X \subset Y ==> mig(X) >= mig(Y)
>
> Coercion: mig_F(X) = roundDown_F(mig(X))
>
> Property still holds although intervals of sufficiently small
> mignitude may have 0 reported if F has insufficient dynamic
> range to express such a small number (all others are finite &
> positive). The property still holds & this is generally not
> a problem as it is a fault of F rather than the definition of
> mignitude.
>
> ----------
>
> Note: wid takes arguments in IRbar & returns results in Rbar+.
>
> Level 1: wid(X) = if (X==Empty) then 0
> else if (X==Entire) then +inf
> else sup(X) - inf(X)
You can remove "else if (X==Entire) then +inf" as it is not a
particular Level 1 case (see also my other remarks below).
> 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
The "else if" clause is at Level 1, where NaN doesn't exist and some
mathematical Rbar operations are well-known (and there are no Level 1
implementations, so no such broken systems at Level 1). Operations are
specified in the standard or by other standards or conventional rules,
not by broken systems anyway.
Note that such formulas are used for specification, not to say that
functions could be implemented by using them directly (in particular,
this could be incorrect due to rounding).
> (there are still such systems around). After that, there is
> guaranteed to be one finite term in the "else" clause. At
> least at level 1. Both John & Vincent argue that wid(Empty)
> = -infinity on much the same grounds as mag(Empty) = -infinity.
> I prefer 0 on Least Astonishment grounds but would have no
> great objection to the change. Vincent provided me with the
> definition that accomplishes that.
>
> ----------
>
> Note: rad takes arguments in IRbar & returns results in Rbar+.
>
> Level 1: rad(X) = if (X==Empty) then 0
> else mag(X - mid(X))
>
> Property: X \subset Y ==> rad(X) <= rad(Y)
>
> Coercion: rad_F(X) = if (X==Empty) then 0
> else mag_F(X - mid_F(X))
assuming that the not-yet-specified mid_F(X) is finite, otherwise
the formula doesn't make sense.
> This one is a bit tricky. Partially due to its use of mid &
> partially otherwise. 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 whether or not it is in the interior of X & (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
Yes, it is important to understand that (you should use _F since the
real difference is at Level 2). They have different practical goals.
> differently. With this definition (courtesy of Vincent), we
> cannot have rad(X) > wid(X). Vincent also notes that the width
> of an interval is unaffected by translation. Thus, an infinite
> interval is still infinite no matter how you shift it (at least
> at level 1). The real problem would come from the subtraction
> of infinities at level 2. And this is avoided by clamping all
> midpoints to finite values.
>
> ----------
>
> Level 1: midRad(X) = for non-empty X only: <mid(X),rad(X)>
>
> Property: mid property holds for mid part & rad for rad.
>
> Coercion: midRad_F(X) = <mid_F(X),rad_F(X)>
I wouldn't like midRad_F(Empty) to be (0,0) at Level 2 (thus ditto at
Level 1), which corresponds to [0,0] = { 0 }, even though it includes
Empty. Indeed, Empty should propagate (except on union).
> This is a derived function, really. And dependent on mid() as
> well. So its behavior is derived from its components. Kind of
> by definition of midRad, we have that its version of (22) namely
>
> X \subset midRad_F(X)
>
> holds so long as not both mid_F(X) & rad_F(X) are infinite &
> mid(X) not NaN. BTW, this suggests to me that we might define
> an infSup(X) which returns [inf(X),sup(X)]. And maybe both this
> & midRad belong elsewhere than table 4.
--
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)