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?)
For some implicit types it obeys, but there is implicite type that violates.
Th1. Suppose that all intervals [u,v] in an implicit datatype satisfy -Fmax <= u <= v <= Fmax .
m = midpoint([u,v]) = roundNear((u + v)/2)
r = radius([u,v]) = roundUp(max(m - u, v - m))
Then r <= Fmax .
We use such facts about roundNear :
roundNear(-x) = -roundNear(x)
x >= 0 => 0 <= roundNear(x) <= x*2
Proof.
A) u = -v
Then m = 0
Then r = roundUp(v) <= Fmax
B) u > -v
(u + v)/2 > 0
0 <= m <= u + v
m - u <= v <= Fmax
v - m <= v <= Fmax
Hence radius <= Fmax
C) u < -v - similar as B
Th2. Suppose implicite interval type with midrad representation
(m,r) = [m-r,m+r], m \in F r \in F.
Then midpoint([m-r,m+r])=m, radius([m-r,m+r])=r <= Fmax
Proof. midpoint([m-r,m+r])=roundNear((m-r+m+r)/2)=roundNear(m)=m,
radius([m-r,m+r])=roundUp(max(m-(m-r),(m+r)-m))=roundUp(max(r,r))=roundUp(r)=r
Example3. Suppose implicite interval type with representation
X=(l0,r0,l1,r1)=[l0+l1,r0+r1], l0 \in F, l1 \in F, r0 \in F, r1 \in F .
Lets us take (-Fmax,Fmax,-Fmax,Fmax)=[-2*Fmax,2*Fmax]
m=midpoint(X)=0
r=radius(X)=roundUp(max(0-(-2*Fmax),2*Fmax-0))=roundUp(max(2*Fmax,2*Fmax))=roundUp(2*FMax)=+oo
-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