0

I need to find three values x,y,z of type Double, such that (x + y) + z == 1.0 and x + (y + z) == 0.0. I'm trying to solve this problem on Scala. This problem has to do with Is floating point math broken? but how i'm supposed to find such values? Is there any algorithm to complete this task? From what i have read, if the denominator is the power of two it is converted to floating point without an error. I tried values like 0.5, 1, 0, 0.25 still no success. Can anyone help me?

Community
  • 1
  • 1
user_777
  • 121
  • 3
  • See what happens when you mix really big values and really small values for `x`, `y`, and `z`. You want the magnitudes of the numbers to differ by a factor around 10^16 or 10^20. – tmyklebu Mar 09 '15 at 18:05
  • Does not work. Tried with : val x: Double = 1e20 val y: Double = 1e-20 val z: Double = 1e-20 – user_777 Mar 09 '15 at 18:26
  • 1
    If you are familiar with the principles of constraint solving, then your question is subsumed by this question and its answer: http://stackoverflow.com/questions/24222822/fastest-algorithm-to-identify-the-smallest-and-largest-x-that-makes-the-double-p , which, well used, would allow you to enumerate all such triples. – Pascal Cuoq Mar 09 '15 at 18:39
  • 2
    A hint: you could look for large magnitude (and opposite sign) `x` and `y`, so that `x + y` is zero. That would leave the choice of `z` as `1.0`. – Pascal Cuoq Mar 09 '15 at 18:40
  • 1
    @PascalCuoq Thank you very much you helped me to solve the problem! I used the following values: val x: Double = 1e19 val y: Double = -(1e19) val z: Double = 1 – user_777 Mar 09 '15 at 18:54

1 Answers1

4

With the right values of x, y, and z it is possible to get 1.0 and 0.0 exactly, without having to use an epsilon on the comparison. I wrote my program in Java, but the principle will carry across to other languages that use IEEE 754 64 bit binary floating point for Double.

public class Test {
  public static void main(String[] args) {
    double x = -Math.pow(2.0, 53);
    double y = 1.0;
    double z = -x;
    System.out.println((x + y) + z == 1.0);
    System.out.println(x + (y + z) == 0.0);
  }
}

[-Math.pow(2.0, 53), Math.pow(2.0, 53)] is the range of doubles in which all integer values are exactly representable. Outside that range, all odd numbers have to be rounded. Increasing the magnitude at either end by 1 requires rounding, and round to even goes back to itself.

x + y, with opposite signs, is inside the range and exactly representable. Adding z to the result gets 1.0, the real number result of the addition. On the other hand, y + z has equal signs, making the magnitude too large for odd integers to be exactly representable, so it rounds to z, and adding x results in 0.0.

Patricia Shanahan
  • 25,849
  • 4
  • 38
  • 75
  • Nitpick: Is `Math.pow` in Java guaranteed to give a result that isn't bogus? In particular, can it give you a number that's off by 1.0 ulp if, for instance, the underlying platform's math library does so? – tmyklebu Mar 09 '15 at 20:13
  • 2
    @tmyklebu "If both arguments are integers, then the result is exactly equal to the mathematical result of raising the first argument to the power of the second argument if that result can in fact be represented exactly as a double value." [Math.pow](http://docs.oracle.com/javase/8/docs/api/java/lang/Math.html#pow-double-double-) – Patricia Shanahan Mar 09 '15 at 20:16
  • The issue @tmyklebu raised is an important one. I knew where to find the answer because I had checked into it the first time I wanted to use `Math.pow` in a context that required exactness. The program could have been written using the corresponding literal, 9007199254740992.0, and it should be done that way in any language without a power function.that is documented to be exact in this case. – Patricia Shanahan Mar 09 '15 at 20:33