Monthly Archives: June 2016

Mean of two floating point numbers can be dangerous

Today I discovered an interesting bug in my code. I had a list of one dimensional points of type double and wanted to find a value somewhere in between to split the list into two lists based on the <= relation. I computed the splitting point by finding a best place in the list and computing the exact split value as a mean of 2 ordered neighboring points:

This  worked fine until the following happened:

Notice that the 2 points differ only in the least significant bit of the mantissa. This means that there doesn’t exist any middle point in the binary representation and on my hardware it caused the splitValue to be equal to point2. Because I used the <= relation and these two points were at the end of the list this meant that no splitting actually happened and it sent my code into infinite recursion until stack overflow happened.

I solved it by extending the code to the following:

If the above situation happens the splitValue is assigned the value of the lesser point. This ensures that the split always splits the list because the right point (point2) is strictly greater than the left point.