Re: Accuracy of cancellative addition and subtraction

[Marco Nehmeier <nehmeier@xxxxxxxxxxxxxxxxxxxxxxxxxxx>]

Dear John, Dear P1788,

may I am wrong and I am not seeing the problem. But I think that the following code
is sufficient to compute cancellative subtraction for inf-sup intervals with bounds of
a floating point type supporting correctly rounded subtraction  (like IEEE 754 bin64)
with a tightest accuracy.

cancelMinus(x, y):
    if (is_unbounded(x) || is_unbounded(y))
        return ENTIRE;

    if (is_empty(x))
        return EMPTY;

    if (is_empty(y))
        return ENTIRE;

    // wid(x) < wid(y) using error free transformations
    (x1,x2) = twoSum(x_upper, -x_lower);
    (y1,y2) = twoSum(y_upper, -y_lower);   
    if (x1 < y1 || (x1 == y1 && x2 < y2))
        return ENTIRE;
   
    return [ sub_rndDown(x_lower, y_lower), sub_rndUp(x_upper, y_upper) ];


Hence the example cancelMinus([Max,Max],[-Max,-Max])in §12.12.5 will correctly compute
hull([2 * Max, 2 * Max]) = [Max, Inf] because of sub_rndDown and sub_rndUp.

For the other example cancelMinus([-1,a],[-b,1])(*) with a,b positive floating point numbers less
then the roundoff unit u, I see no reason why it it contradicts the requirement of a tightest accuracy.
The problem is that in the case of a < b the width (**) of both intervals
is computed as 1 + u and not as 1 + a and 1 + b. But with the use of error free transformations (***) this can
be easily avoided.


Hopefully I have not overlooked other tripping hazards...
I suggest to change

"12.10.2. Accuracy requirements. Following the categories of functions in Table 9.1, the accu-
racy of the basic operations, the integer functions and the absmax functions shall be tightest."

into

"12.10.2. Accuracy requirements. Following the categories of functions in Table 9.1, the accu-
racy of the basic operations, the integer functions and the absmax functions as well as the
cancellative addition and subtraction in §10.5.6 shall be tightest."


Best regards

Marco



(*) I guess that cancelMinus([-1,a],[-b,1) in §12.12.5 is a Typo and it should be cancelMinus([-1,a],[-b,1])
(**) using the formula upper - lower
(***) or complete arithmetic




On 17.06.2014 12:38, John Pryce wrote:

Marco

It seems you are right, thanks for pointing out this omission. Will you suggest the needed change to the wording of 12.10.2, please?

I disagree about your "obviously", below. See the examples in 12.12.5. It may be quite easy but it is also easy to get it wrong. If you have an algorithm that makes it simple, ensure that this is posted on the "tips for implementers" part of the 1788 web site.

John Pryce

On 17 Jun 2014, at 09:52, Marco Nehmeier wrote:

Dear John,

I guess in §12.10.2 the accuracy requirements for cancellative addition and subtraction is missing.
Obviously a tightest implementation of these operations is quite easy.
But I think we should add the accuracy information for cancellative addition and subtraction in §12.10.2 to avoid ambiguity.

Best regards

Marco

-- 
     o           Marco Nehmeier, Lehrstuhl fuer Informatik II
    / \          Universitaet Wuerzburg, Am Hubland, D-97074 Wuerzburg
InfoII o         Tel.: +49 931 / 31 88684
  / \  Uni       E-Mail: nehmeier@xxxxxxxxxxxxxxxxxxxxxxxxxxx
 o   o Wuerzburg