MidRad to/from InfSup (was: the "set paradigm" is harmful)

[Michel Hack <hack@xxxxxxxxxxxxxx>]

> > |     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