> | If xx=[l,u] is compact, m and r shall have the values defined by
> | set round up
> | r = 0.5*(u-l);m=l+r.
That formula is due to Prof. Oishi from Waseda university, Tokyo. See
http://www.ti3.tu-harburg.de/paper/rump/OiRu02.pdf
So we what do make of John Pryce's example?
Input: [0.9993, 1.001] (format: 4-digit Decimal FP)
r = 0.5 * (1.001 - 0.9993) = 0.0008500 (exactly)
m = 0.9993 + 0.0008500 = 1.0001500 (exactly)
= 1.001 (rounded up)
Result: 1.001+-0.0008500 (decimal precision 4 digits)
Hovever, 1.001 +- 0.00085 does not cover the original lower bound,
as the exact range is 1.00015 to 1.00185 -- it is slightly shifted.
Now, the cited paper (after a very quick glance, I have to admit)
does not actually claim that: m-r <= l AND u <= m+r
It claims that a certain quantity X contained in [l, u] is also
contained in [m-r, m+r], and that the MidRad form is easier to
compute and yet as good (or nearly as good) as the InfSup form.
That is an entirely different matter.
For a moment I thought the issue was due to the decimal format,
with its much larger ulp jump at a power of the base. But it
turns out that the same thing happens in binary. Consider a
four-bit binary format:
Input: [0.1111, 1.001] (format: 4-bit Binary FP)
r = 0.1 * (1.001 - 0.1111) = 0.0001100 (exactly)
m = 0.1111 + 0.0001100 = 1.0000100 (exactly)
= 1.001 (rounded up)
Result: 1.001+-0.0001100 (binary precision 4 bits)
Hovever, 1.001 +- 0.00011 does not cover the original lower bound,
as the exact range is 1.00001 to 1.00111 -- it is slightly shifted.
I conclude that the proposed formula does not always provide
a valid MidRad enclosure of a given InfSup interval.
Now I'll open my proposed alternative to attack; my head is spinning:
Set round nearest
m = 0.5 * (l+u)
Set round up
r = max(u-m, m-l);
This is most likely not the fastest way to proceed, but I believe
it always gives a valid enclosure, and when fma is used to compute
the candidate radii u-m and m-l, I think it provides the tightest
enclosure using the given arithmetic.
This all illustrates vividly how tricky this whole business cam be!
Michel.
Sent: 2009-02-11 23:47:21 UTC