Re: Don't get your GI tract in a twist...
> But I note that Dmitry's radius formula seems to obey property (18), too (am
> I wrong?)
I shall try to prove (18) for 754-compatible explicit interval format:
There are only four intervals [u,v] with v - u >= 2*Fbig
[-Fmax,Fmax] midpoint=0 radius = Fmax
[-Fbig,Fmax] midpoint=ulp(Fmax)/2 radius=Fmax
[-Fmax,Fbig] midpoint=-ulp(Fmax)/2 radius=Fmax
[-Fbig,Fbig] midpoint=0 radius=Fbig
For other intervals v - u < 2*Fbig
Let m = midpoint([u,v])
We have abs( m - (u+v)/2 ) <= ulp(Fmax)/2
This means (u+v)/2 - ulp(Fmax)/2 <= m and m <= (u+v)/2 + ulp(Fmax)/2
From the first inequality
v - m <= ulp(Fmax)/2 + (v-u)/2 < ulp(Fmax)/2 + Fbig < Fmax
From the second inequality
m - u <= (v-u)/2 + ulp(Fmax)/2 < Fbig + ulp(Fmax)/2 < Fmax
Hence radius([u,v]) <= Fmax .
I need to think more about implicit formats.
> My main question is can we always assume optimzation (*) works over more
> general definition (**) for every conceivable floating-point representation
> (even non-IEEE 754 formats)? Or should we specify (**) but let implementers
> choose optimzation (*) if it is safe for thier particular floating-point
> formats?
Yes. The (*) and (**) are equivalent for any explicit or implicit interval type
provided that number format is symmetrical: (v \in F) <=> (-v \in F) .
Let us consider 3 cases:
1) u <= m <= v
(**) max(abs(roundDown(u-m)),abs(roundUp(v-m))) = max(abs(-roundUp(m-u)),abs(roundUp(v-m)) =
max(roundUp(m-u), roundUp(v-m)) = roundUp(max(m-u,v-m)) (*)
2) m <= u <= v (This may happen only with implicit interval type)
(**) max(abs(roundDown(u-m)),abs(roundUp(v-m))) = max(roundDown(u-m),roundUp(v-m)) = roundUp(v-m)
(*) roundUp(max(m - u, v - m)) = roundUp(v-m) (because v-m>=0 and m-u<=0)
3) u <= v <= m (This may happen only with implicit interval type)
(**) max(abs(roundDown(u-m)),abs(roundUp(v-m))) = max(abs(-roundUp(m-u)),abs(-roundDown(m-v))) =
= max(roundUp(m-u),roundDown(m-v))=roundUp(m-u)
(*) roundUp(max(m - u, v - m)) = roundUp(m-u) (because m-u>=0 and v-m<=0)
Best regards.
-Dima
----- Исходное сообщение -----
От: nh@xxxxxxxxxxxxxxxxx
Кому: intervals08@xxxxxxxxxxxxxx, dmitry.nadezhin@xxxxxxxxxx
Копия: stds-1788@xxxxxxxxxxxxxxxxx
Отправленные: Вторник, 31 Январь 2012 г 17:43:41 GMT +03:00 Москва, Санкт-Петербург, Волгоград
Тема: Re: Don't get your GI tract in a twist...
Dan Zuras wrote:
>> What about one more example (again in two-digit floating-point decimal
>> numb=
>> ers) ?
>>
>> [u,v] = [0.92,1.2]
>> midpoint([u,v]) = roundNear((u + v)/2) = roundNear((0.92 + 1.2)/2) = =
>> roundNear(1.06) = 1.1
>> radius([u,v]) = roundUp((v - u)/2) = roundUp((1.2 - 0.92)/2) = roundU=
>> p(0.14) = 0.14
>> [roundDown(midpoint(X) - radius(X)), roundUp(midpoint(X) + radius(X))] =
>> =
>> [roundDown(1.1 - 0.14), roundUp(1.1 + 0.14)] =
>> [roundDown(0.96), roundUp(1.24)] = [0.96, 1.3]
>>
>> The property ([0.92,1.2] \subset [0.96, 1.3]) is false.
>>
>
> Now, THAT'S a good example.
>
> OK, we're wrong. (I'm wrong. I had to convince Nate. :-)
Yes, I had some cold feet about this one :-)
But I note that Dmitry's radius formula seems to obey property (18), too (am
I wrong?)
Dmitry Ndezhin wrote:
> There tightest radius(X) satisfing (22) is:
> radius([u,v]) = roundUp(max(midpoint([u,v]) - u, v - midpoint([u,v]))) .
> (*)
> However, it is necessary to explore if it can be implemented efficiently.
I spent some time looking at a smiliar formula on Saturday. If m =
midpoint([u,v]) then I had come up with:
radius([u,v]) = max(abs(roundDown(u-m)),abs(roundUp(v-m))) (**)
But your formula (*) above is better, since it recognizes v-m is always
positive and u-m is always negative, hence saving two absolute values and a
rounding mode switch.
My main question is can we always assume optimzation (*) works over more
general definition (**) for every conceivable floating-point representation
(even non-IEEE 754 formats)? Or should we specify (**) but let implementers
choose optimzation (*) if it is safe for thier particular floating-point
formats?
Otherwise its hard for me to think how (*) or (**) might be implemented more
efficiently.
Nate