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) = 0x1.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) for
all finite u \in F, v \in F, u <= v .
> 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 interval 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 contained in [0,1].
The (15) midpoint_64([u,v])
1) midpoint([0,+Infinity[)=roundUp((Fmax + 0)/2)=roundUp((1.fffffffffffffp1023 + 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.fffffffffffffp1023]
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 .
IMHO midpoint(X) for central form and split(X) for B&B should be
different functions.
-Dima