Re: Midpoint paper (2012-02-08 version)
> Date: Sun, 12 Feb 2012 11:57:03 -0800 (PST)
> From: Dmitry Nadezhin <dmitry.nadezhin@xxxxxxxxxx>
> To: <intervals08@xxxxxxxxxxxxxx>
> Cc: <stds-1788@xxxxxxxxxxxxxxxxx>
> Subject: Re: Midpoint paper (2012-02-08 version)
>
> Dan,
>
> > Indeed, let me mention that this entire discussion
> > is outside the scope of the proposal that Nate & I
> > are making.
>
> Even the discussion is outside the scope, it is very close to it.
>
> I suppose that "midpoint" operation is another name of the required numeric=
> function of interval "mid"
> that is defined in Table 4 of DRAFT 04.3 . If "midpoint" is a new function =
> then my emails are really out of the scope.
No, you are correct. The midpoint that Nate & I are
trying to characterize is intended as a replacement for
John's mid function.
It is just that the scope of our definition was intended
for the generic context. That is, when the floating-point
type of the result is the same as that used in the input
interval. Similarly, the scope of John's mid excludes
Empty, Entire, & all the semi-infinites.
Perhaps we erred in not generalizing to formatOf versions.
But that is what we did.
>
> The objective of your proposals is "to define width and midpoint operations=
> for P1788
> intervals in such a way that the operations are useful for numerical method=
> s
> involving centered forms and bisection algorithms that require the
> splitting or shrinking of intervals."
>
> The current "Midpoint paper" succeed to find the operation for two common i=
> nterval datatypes:
> the argument is of infsup interval datatype T derived from the number forma=
> t F and the result is of F;
> the argument is of midrad interval datatype T derived from the number forma=
> t F and the result is of F.
> I shall name these datatype infsup-F and midrad-F.
>
> However, the current draft for Level 2
> http://grouper.ieee.org/groups/1788/email/msg04488.html
> mentions in 6.3.1 arbitrary interval datatype T that is not tied to any
> number format F. I suppose that the standard will have a common definition =
Hmm. That's not how I read that definition. It looks
to me that a bare interval type is a collection of
ordered pairs (x,t) where x is either Empty, Entire,
or an element of t, where t is the unique name for an
interval type. That set is finite in x for any given
t although there may be an unbounded number of t's.
> of "mid" function
> both for infsup-F/midrad-F datatype and as well for arbitary datatypes.
Yes, I believe this is so. But since t is an explicit
component of a bare interval type, it is not yet
established whether or not the definition of mid (or
any other function, for that matter) is a function of t.
It could go either way. One way for some functions, &
the other for others.
>
> Hence, IMHO, the attempt to explore definitions of "mid" for arbitrary data=
> types
> is close to the scope of definition of "mid" for infsup-F/midrad-F.
Granted.
It could even be within the scope for some definitions
of mid. For example, Michel's definition could be
stated
midpoint(X) = if (X == Entire) then 0
else (inf(X)+sup(X))/2
as a level 1 definition, generic to all t's, that makes
no reference to t. Our definition could be stated as
midpoint(X) = if (X == Entire) then 0
else if (inf(X)==-inf) then (sup(X)-Fmax(t))/2
else if (sup(X)==+inf) then (inf(X)+Fmax(t))/2
else (inf(X)+sup(X))/2
which requires some knowledge about t (Its Fmax).
Both can live at level 1. Both can be coerced to t
to get to level 2. Although the coercion must take
a special finite-only flavor like
coerce2finite_t(m) = min(max(t,-Fmax(t)),Fmax(t)).
I like to think our definition is better but I'm having
my doubts. In the generic case it wins for semi-infinite
numbers. But if the existence of a level 1 definition is
required to include the formatOf cases, Michel's seems
simpler if a bit less useful among the semi-infinites.
>
> I see that there are two opinions about midpoint of narrow intervals:
> midpoint([1+u^2,1+2*u^2])=1 or midpoint([1+u^2,1+2*u^2])=NaN .
> So I retain from considering midpoint on narrow intervals for a while .
I think this problem is more general than any specific
definition of midpoint. It has to do with the nature
of the interval representations themselves & their
relationship to other (different) floating-point types.
If we are to come up with the solution to this, I think
we have to consider the larger context as well.
For example, if the defining charecteristic of midpoint
is that it returns some value within the interior of the
input interval, then midpointFloat([1+u^2,1+2*u^2])=NaN
is justified on the grounds that there IS NO interior
point among the floats.
However, if the defining charecteristic of midpoint is
returning an interior point then even the generic form
has the 2 point interval
midpoint([x,x+ULP(x)]) = NaN (1)
on the grounds that there are only 2 points in the
interval, both of which are endpoints. The same can
be said for the 1 point interval
midpoint([x,x]) = NaN (2)
& the 0 point interval
midpoint(Empty) = NaN. (3)
I think the user would be justifiably astonished upon
finding that, just as the interval has been narrowed
as far as it can, the midpoint is suddenly undefined.
It seems the user would be better served if (1) & (2)
returned one of their endpoints. But (3) is still a
problem. In short, "interiorness" can be a desirable
charecteristic of midpoint but it can not be a defining
one.
Now, let's assume that any level 2 midpoint is the
coercion of some level 1 value. Under that assumption,
any midpoint that has an extended Real value at level 1
should have a nearest (finite) value at level 2. Any
strange things that happen along the way (out of interior,
clamped to finite, et al) are properties of the coercion
not properties of the midpoint. Thus,
midpoint([x,x+ULP(x)]) = either x or x+ULP(x),
midpoint([x,x]) = x,
& midpoint(Empty) is still a problem.
>
> I still have some feeling that part of definition (15) mid_F([u,+oo[) = u=
> lp((u + Fmin)/2) is unnatural.
I assume you meant to type roundUp((u+Fmax)/2).
But let's go with it for the sake of argument...
> Informally, the semi-infinite right side is "larger" than finite left size.=
>
> I searched for example. And I found one that seems to be in the infsup-F/mi=
> drad-F scope.
>
> Consider interval datatype T = infsup-F \union midrad-F .
> Representation of this interval datatype is (F,F,bool) .
> bool flag says if it is infsup or midrad .
> Consider two intervals from T: midrad <Fmax,Fmax>=[0,2*Fmax] and infsup [=
> 0,+oo[ .
> The formula (15) gives
> mid_F([0,2*Fmax])=roundNear((0+2*Fmax)/2)=roundNear(Fmax)=Fmax .
> mid_F([0,+oo[)=roundUp((0+Fmax)/2)=roundUp(Fmax/2)=Fmax/2
This is slightly different for decimals, but I take
your point.
> The monotonic property (10) fails for this interval datatype.
So it does.
I have never heard anyone propose such an interval
type. It is certainly outside the scope of the 1788
draft as I understand it.
And you have just given a good reason why it should be. :-)
>
> The Michel's suggestion that mid_F([u,+oo[)=Fmax passes property (10).
> >>
> >> This suggests that the midpoint of a semi-bounded interval should
> >> simply be Fmax (or -Fmax) -- these will certainly be Interior points.
> >
> > Yes, we looked at this. And it would work in its own fashion.
> > But we concluded that for the desired application, that of
> > narrowing an interval by some means, choosing an interior
> > point near (lo+Fmax)/2 was more useful. Indeed, that was
> > the lowest point we could choose & still maintain weak
> > monotonicity. For "wide" semi-infinite intervals it is
> > still no where near the mean of the list of representable
> > numbers (which would split our task into 2 equal parts).
> > But it is the best we can do short of that.
>
> The "(lo+Fmax)/2" definition saves 1 iteration of 1025 .
> The advantage of "Fmax (or -Fmax)" definition is simlicity and regularity.
Both are true.
>
> Also, the "Fmax (or -Fmax)" definition enables monotonic extension of mid_F=
> (X) on arbitrary interval type T.
> Either with mid([1+u^2,1+2*u^2])=1 or with mid([1+u^2,1+2*u^2])=NaN .
>
> -Dima
Yes, I understand.
I still like the idea of splitting a semi-infinite
interval near (lo+Fmax)/2 but I can see, in the case
of formatOf functions, a level 1 midpoint more along
the lines of Michel's would be easier to define.
John, this task will ultimately fall to you. How
would YOU like to write it?
And any thoughts on midpoint(Empty)?
Dan