How is addition of double is done here and a valid way to detect that the result could not be represented

Question

I am trying to understand double a bit better. In the following code snippet min and max are double:

double min = 3.472727272727276;
double max = 3.4727272727272767;
System.out.println(max - min);  
System.out.println((max - min)/2);
double mid = min + ((max - min)/2);
if(min == mid) {
    System.out.println("equal");
}
System.out.println(mid);

The first 2 print statements print:

4.440892098500626E-16
2.220446049250313E-16

Which basically is:
0.0000000000000004440892098500626 and 0.0000000000000002220446049250313

Then the conditional check is true i.e. prints equal and the last print is: 3.472727272727276

So from my understanding the (max - min)/2 gave a value that could be represented by a double.
What is not clear to me is what is happening during the addition.

1. Is the addition creating a number that could not be represented by a double and leaves the original min as is by dropping of digits or is the number effectively considered as 0 before the addition actually happens or how exactly is this done?
2. Is the min == mid a valid check to detect such issues with doubles? I.e. with integer we can detect overflow/underflow by checking if the result is less that we started with. Is the equality check after doing an addition a sane/reasonable check to detect the equivalent problem with double i.e. that the number added was not really enhanced due to rounding error (or what exactly is the actual term for this)?

Answer 1

For this example, it is easy to see what is happening by viewing the numbers in a hexadecimal floating-point format. The result of converting the source text 3.472727272727276 to double is 3.47272727272727621539161191321909427642822265625, which, using hexadecimal, is:

    1.BC8253C8253D016•21

Observe there are exactly 53 bits in the significand—one before the “.” and 52 in 13 hexadecimal digits after it. The double format has one bit for the sign, 11 for the exponent, and 53 for the significand. (52 are stored explicitly; one is encoded via the exponent.)

Converting the source text 3.4727272727272767 to double yields 3.472727272727276659480821763281710445880889892578125, which is:

    1.BC8253C8253D116•21

Now we can easily see what happens with arithmetic on them. Their difference is:

    0.000000000000116•21

When we normalize that, it is 1.₁₆•2¹⁻⁵² = 1.₁₆•2⁻⁵¹ ≈ 4.44•10⁻¹⁶, and the double format can easily represent half of that simply by adjusting the exponent. Then we have 1.₁₆•2⁻⁵² ≈ 2.22•10⁻¹⁶.

However, when we try to add that halved difference to the first number, the result with real-number arithmetic is:

    1.BC8253C8253D0816•21

Observe this has 54 bits—one before the “.”, then 52 in 13 hexadecimal digits, and a final one in the high bit of that 14^th digit, the 8. The double format does not have 54 bits in its significand, so addition in double format cannot produce this result. Instead, the sum is rounded to the nearest representable value or, in case of a tie, to the nearest representable value with an even low bit. So the result is 1.BC8253C8253D08₁₆•2¹, which is the same as min.

Answer 2

1. Is the addition creating a number that could not be represented by a double

The algorithm for adding two floating point numbers as a first step brings the two numbers to the same exponent. Effectively this is done by shifting the bits of the smaller number to the right, and the bits that underflow are lost (become zero).

If the calculation is done with 64-bit precision,

3.472727272727276 + 2.220446049250313E-16     or in hex:
0x1.bc8253c8253dp1 + 0x1.0p-52

in effect becomes the calculation

3.472727272727276 + 0.0     or in hex:
0x1.bc8253c8253dp1 + 0x0.0p1

and this happens in hardware, so the intermediate 0.0 value is not stored anywhere or visible as a separate step.

But: it's possible the calculation is done with higher precision than 64 bits. For example if 80-bit precision floating point CPU instructions are available, the JVM is allowed to use them. In that case the intermediate results will be different, but the end result is still going to be the same because the result has to be stored as a 64-bit double.

2. Is the min == mid a valid check to detect such issues with doubles?

Depends on what you need to do. The == operator checks if the two numbers are exactly equal, for better or for worse. In many places people don't want exact equality because it's difficult or impossible to achieve: for example Math.sin(Math.PI) is not going to be exactly 0 but you may prefer to pretend it's "close enough" to 0.

Answer 3

The following code may demonstrate the issue:

double num = 1;
while (!Double.isInfinite(num)) {
    num *= 2;
    System.out.println(num);
}
System.out.println("-----------------------");
System.out.println("-- now the opposite----");
System.out.println("-----------------------");
num = 1;
while (num > 0) {
    num /= 2;
    System.out.println(num);
}

The space in the memory is limited by the number of bits. Thus it is inevitable that at some point a very small number will be exactly zero.

In your calculation, the operators act on doubles creating temporary doubles in the CPU - which also fall under the precision limit and thus in your case become zero

And of course, the == operator must be used with diligence on doubles, but that was not the problem here.

To answer your second question, you need to use BigDecimal instead of double to be on the safe side.

The problem with checking is, that the values that any double can assume are not evenly distributed. Between 0 and 1, there is a similar number of values a double can assume than between 1 and Infinity.

EDIT: yes, the result of mid == min is of course a proof that the double precision limit has been reached. But the inverse mid != min does not prove that the limit may have been reached in another step.

In a general program that operates on arbitrary input doubles you would need to do that sort of check with every intermediate calculation result. I think it is not worth the effort compared to using BigDecimal and also you run the risk of forgetting some checks.