0
$\begingroup$

In finite precision floating point arithmetic the associative property of addition is not satisfied. This is, it is not always the case that $$(a+b)+c=a+(b+c)$$ Even $a=(a+b)-b$ is not always true.

To prove that $x+y<z$ is equivalent to $x<z-y$ with real numbers we can add $-y$ on both sides of $x+y<z$ to get $(x+y)-y<z-y$ and then from this $x=x+(y-y)<z-y$. But I can't repeat the last step for floating point.

Question 1: Are the inequalities $x+y<z$ and $x<z-y$ equivalent in finite precision floating point arithmetic?

Question 2: Are the inequalities $x+y\leq z$ and $x\leq z-y$ equivalent in finite precision floating point arithmetic?

I was too hasty and updated without checking properly. What I really indented to ask is if the breaking of the equivalence could be as drastic as:

Question 3: Could we have $x+y<z$ and $x>z-y$?

Possibly there are already answers below for this. If so, I will check them when I get a chance and select the answer.


Motivation: There is that interview problem that given an ordered array of numbers and a threshold it asks for the number of pairs of numbers of the array which sum is not larger than the threshold. Possible solutions aside, I wanted to understand the particular point of the dangers of switching between testing $x+y<z$ (and also $\leq$ depending on which variant of the problem is presented) and testing $x<z-y$ (or $\leq$).

$\endgroup$
1
$\begingroup$

Consider the case that x and y hold the largest representable value for the current type, and z is positive infinity. By the rules of floating point arithmetics, x + y is now infinity, which isn't less than infinity. On the other hand, z - y is also infinity, which the largest representable value is less than.

Another example would be when x is very small negative, and y = z and much larger in magnitude than x. Then x + y = y = z, but z - y = 0, which is larger than x.

The examples work for your second question as well if you flip the signs of all numbers - !(l > r) is nearly equivalent to l <= r. NaNs break the equivalence, but those aren't useful as examples to your question anyways.

$\endgroup$
2
  • $\begingroup$ In both of these examples the failing inequality is an $=$. Do you know if there are examples in which the failing inequality has the reverse sign? A failure for the equivalence with $\leq$. $\endgroup$ – plop Jul 5 '20 at 13:14
  • $\begingroup$ I don't believe that's possible. The right hand side is closer than the result of an operation than any value below/above the right hand side value whichever is away from the accurate result. $\endgroup$ – John Dvorak Jul 5 '20 at 13:36
1
$\begingroup$

Take x=1+u, y=1+2u, z=2+4u, where u is the value of the lowest mantissa bit. x+y = 2+3u gets rounded up to 2+4u, so x+y<z is false. z-y = 2+4u - (1+2u) = 1+2u, so x < z-y is true. That’s a counter example for the first case.

With x=1+3u you get a counter example for the second case.

$\endgroup$
1
  • $\begingroup$ In the second example, do we have $x+y=\operatorname{round}(2+5u)=2+6u>2+4u=z$ and $x=1+3u>1+2u=z-y$? $\endgroup$ – plop Jul 6 '20 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.