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:

1 |
splitValue = (point1 + point2) / 2.0; |

This worked fine until the following happened:

1 2 3 4 |
Binary representations of the floating point numbers in IEEE-754: point1: 1011111111011101110111011101111101000011110001111101010111101101 point2: 1011111111011101110111011101111101000011110001111101010111101100 |

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:

1 2 3 4 |
splitValue = (point1 + point2) / 2.0; if (splitValue == point2) { splitValue = point1; } |

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.