Re: Midpoint paper (2012-02-08 version)
Dan,
I read the last version of "Midpoint paper".
And it seems to me that it is good for explicit infsup interval types.
Then I started to think about abitrary imlicit interval types.
What will be the results of midpoint_F([u,v]) definition of (15)
when u and v don't belong to number format F.
Initially I thought about the representation (r;a;b) = [r + a, r + b] where r \in F, a \in F, b \in F.
I found that sometimes midpoint of a finite interval becomes infinite.
Let us consider 2-digit decimal numbers with the exponent range from -9 to +9 .
The (r;a;b) = (9.9e+9;0;1.0e+8) .
Then (15) says that midpoint([r+a,r+b])=midpoint([9.9e9;1e10])=
roundNear((9.9e9 + 1.0e10)/2)=roundNear(9.95e9)=+Infinity .
That was my original complaint.
I desired such a property:
(*) midrad([u,v]) is finite floating-point number for finite [u,v] intervals (explicit or implicit).
The definition (15) may return infinite midpoint for some finite implicit intervals.
Then I read the Michel's post. It was about semi-finite interval of wider format,
but it came to me the same may happen
with midpoint_F([u,v]) Level 2 operation that maps infsup intervals [u,v] of wider IEEE-754 format Fw to
narrower IEEE-754 format F.
So the question that bothers me is:
What properties do we expect from width(X)/midpoint(X)/radius(X) when
X is of implicit interval type or X is of explicit interval type of wider number format ?
I concern about central form application of functions midpoint(X),radius(X).
The property (*) is important for this purpose.
> One MIGHT solve that problem by something like:
>
> midpoint([u,v]) = if ((u==-inf) && (v==+inf)) then 0
> else if (u==-inf) then { if (v>-Fmax32) then -Fmax32 else -Fmax64 }
> else if (v==+inf) then { if (u<Fmax32) then Fmax32 else Fmax64 }
> else roundToNearest((u+v)/2)
>
> That way both single & double precision semi-infinite
> intervals would go through the same sequence of
> midpoints but for the fact that [Fmax32,+inf] is
> further splittable in double but not in single.
> THIS is a function that addresses Michel's original
> complaint. But now we have a function that is specific
> to systems that support binary32 & binary64, no more &
> no less. A system that supports, say, decimal64 &
> decimal 128 would be different. As would a system that
> supports multiple (possibly unbounded) larger precisions
> no matter the radix.
I spoke about midpoint_F([u,v]) operation that maps arbitrary real interval [u,v]
to the fixed format F. My definition used only Fmax and -Fmax elements of the set F.
So I think that it was not binary32-specific .
-Dima
----- Исходное сообщение -----
От: intervals08@xxxxxxxxxxxxxx
Кому: dmitry.nadezhin@xxxxxxxxxx
Копия: stds-1788@xxxxxxxxxxxxxxxxx, intervals08@xxxxxxxxxxxxxx
Отправленные: Пятница, 10 Февраль 2012 г 19:14:15 GMT +03:00 Москва, Санкт-Петербург, Волгоград
Тема: Re: Midpoint paper (2012-02-08 version)
> Date: Fri, 10 Feb 2012 03:38:42 -0800 (PST)
> From: Dmitry Nadezhin <dmitry.nadezhin@xxxxxxxxxx>
> To: <hack@xxxxxxxxxxxxxx>, <intervals08@xxxxxxxxxxxxxx>
> Cc: <stds-1788@xxxxxxxxxxxxxxxxx>
> Subject: Re: Midpoint paper (2012-02-08 version)
>
> Michel, Dan, P1788
>
> > This suggests that the midpoint of a semi-bounded interval should
> > simply be Fmax (or -Fmax) -- these will certainly be Interior points.
>
> I like this suggestion...
>
> > But in fact I think my rule is better in an environment that supports
> > multiple precisions. Consider [low, +Inf]_64 where low < Fmax32 for
> > example. This interval can also be represented as [low, +Inf]_32.
> > Now lets take midpoints. Converting a midpoint to a narrower range
> > should round towards zero to preserve the finiteness property. With
> > my rule taking midpoint and converting from binary64 to binary32 would
> > commute (both paths ending up with Fmax32), but with rule (15) the
> > midpoints would be different.
>
> ... especially in multiprecision environment.
> There is an issue even for finite intervals in such an environment.
> The maximal power of two in Binary32 number format is 0x1.0p127 .
> The Fmax in Binary32 is 0x1.fffffep127 .
> Suppose Binary64 singleton finite interval [u,v]=[0x1.0p128,0x1.0p128] .
> According to (15)
> midpoint_64([u,v]) = roundNear_64((u+v)/2) = roundNear(0x1.0p128) = 0=
> x1.0p128 ;
> midpoint_32([u,v]) = roundNear_32((u+v)/2) = roundNear(0x1.0p128) = +=
> Infinity .
>
> A possible definition that can handle multiple precisions is
> midpoint([u,v]) = if (u == -Infinity && v == +Infinity) then 0
> else if (u + v >= 0) min( roundNear((u + v)/2) , Fmax )
> else max( -FMax , roundNear((u + v)/2) )
> According to this definition
> midpoint_32([u,v]) = min( roundNear_32((u+v)/2, 0x1.ffffffep127 ) = min=
> ( +Infinity, 0x1.ffffffep127) = 0x1.ffffffep127 = Fmax_32
>
> It seems that this definition satisfies (10).
> Also this definition of midpoint_F([u,v]) returns the same result as (15) f=
> or
> all finite u \in F, v \in F, u <= v .
If the complaint is that the midpoint of semi-infinite
intervals of one precision is not the same as those of
another, this is not the cure. It ALSO returns a
midpoint that is a function of the precision involved.
One MIGHT solve that problem by something like:
midpoint([u,v]) = if ((u==-inf) && (v==+inf)) then 0
else if (u==-inf) then { if (v>-Fmax32) then -Fmax32
else -Fmax64 }
else if (v==+inf) then { if (u<Fmax32) then Fmax32
else Fmax64 }
else roundToNearest((u+v)/2)
That way both single & double precision semi-infinite
intervals would go through the same sequence of
midpoints but for the fact that [Fmax32,+inf] is
further splittable in double but not in single.
THIS is a function that addresses Michel's original
complaint. But now we have a function that is specific
to systems that support binary32 & binary64, no more &
no less. A system that supports, say, decimal64 &
decimal 128 would be different. As would a system that
supports multiple (possibly unbounded) larger precisions
no matter the radix.
These things can be made to work but I see no way of
making them standard or portable in any real sense of
the words. To do that one would have to write midpoint
with no reference to the underlying floating-point at
all. I don't know how to do that, maintain weak
monotonicity, & not get infinite split points.
Then again, neither do I see that the complaint causes
any difficulty for anyone. So I must say I am
disinclined to change it on that basis.
Is there any other more serious complaint?
>
> > I certainly would not want the standard to allow mid(m;a;b) blindly
> > to return "m". Now, computing "m" from the representation may indeed
> > return "m" due to rounding, and perhaps that's what example 4 tried to
> > illustrate.
>
> Surely. This is a coincidence that midpoint(x) = m for particular interva=
> l in the example.
>
> > But surely midpoint(1.0;10;20) would be 15 and not 1.0, right?
>
> Almost right.
>
> midpoint(1.0;10;20) = midpoint([11,21]) = 16
>
> > Perhaps using "m" as the name for the first component is a bad idea.
>
> I agree.
>
> >>
> >> 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.
>
> Consider interval X=[0,+Infinity[. Let us split it many times by midpoint=
> _64([u,v]) .
> Let us look how much steps are necessary to get an interval that is contain=
> ed in [0,1].
And this is a situation for which the mean of the
representable numbers is a cure. But that is a
topic for another day.
>
> The (15) midpoint_64([u,v])
> 1) midpoint([0,+Infinity[)=roundUp((Fmax + 0)/2)=roundUp((1.fffffffffff=
> ffp1023 + 0)/2)=1.fffffffffffffp1022; X1 = [0,1.fffffffffffffp1022]
> 2) X2 = [0,0x1.fffffffffffffp1021]
> ...
> 1023) X1023 = [0,0x1.fffffffffffffp0]
> 1024) X1024 = [0,0x1.fffffffffffffp-1]
>
> The Michel's midpoint_64
> 1) midpoint([0,+Infinity[)=Fmax=1.fffffffffffffp1023; X1 = [0,1.fffff=
> ffffffffp1023]
> 2) X2 = [0,1.fffffffffffffp1022]
> ...
> 1023) X1023 = [0,0x1.fffffffffffffp1]
> 1024) X1024 = [0,0x1.fffffffffffffp0]
> 1025) X1025 = [0,0x1.fffffffffffffp-1]
>
> The (15) saves one step of 1025 .
>
> > At one point, I raised the possibility of the mean of the
> > number of representable elements. For intervals wider
> > than the radix, this amounts to something akin to the
> > geometric mean. And, for intervals containing zero in
> > their interior, it invariably picks a number quite near
> > zero.
> >
> > When I raised the possibility, I thought it would be shot
> > down for much the same reason as similar functions are
> > shot down in floating-point: It is too specific to the
> > floating-point system in question & requires bit twiddling
> > rather than arithmetic to compute.
> >
> > But I was wrong & a number of people thought it might be
> > useful in the interval context. So I may propose it at
> > some later date. But I would like to think about it a
> > bit first.
>
> I also like your "mean of the number of representable elements" suggestion =
> for B&B algorithms .
> For example, the first step of splitting [0,+Infinity[ will be
> [0,0x1.8p0]=[0,1.5] and [0x1.8p0,+Infinity)=[1.5,+Infinity[ .
> It looks better than 1024 steps.
>
> Nevetherless, I would like to get a central form for interval [0,1] with a =
> plain half midpoint
> midpoint([0,1])=0.5
> instead of
> midpoint([0,1])=0x1.8p-512=1.118751109680031E-154 .
And this is one of the faults of the representable split
approach.
Still, in analogy to looking for [0,1] within [0,+inf],
looking for [0,10^-150] within [0,1] takes a long time
with arithmetic mean & is better served by representable
mean. It all depends on what you know about your problem.
>
> IMHO midpoint(X) for central form and split(X) for B&B should be
> different functions.
>
> -Dima
Of course.
Dmitry, you have convinced me that I should come up
with a reasonable definition of a split by the
representable numbers of a system. It is no cure
for the problem of splitting off semi-infinite
intervals as a function of precision but then again
I can see no reasonable cure for that.
Still, it will have its uses. But it is an issue
for another day.
We are discussing the properties of arithmetic forms
of midpoint(), width(), & radius(). Or at least
flavors of those functions that have been slightly
modified to make them as useful as we can for the
applications for which they are intended.
If you can improve upon them as you did with radius()
let's hear about it.
I will make a proposal about a representable form of
split() when I have one. I think it can be done
arithmetically but it will have to know a great deal
about the floating-point within which it sits. At
this time, I believe I can do it for 754-like systems
of floating-point. I am less sure about others.
I'll let you know.
But not today.
Dan