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.

5 thoughts on “Mean of two floating point numbers can be dangerous

  1. David

    The safer way to calculate the mean of two integers is

    min + (max – min) / 2

    I’m guessing this would help this case with doubles as well.

    Reply
    1. Jared

      This would not help. The issue isn’t one of overflow, the issue is that any two adjacent doubles do not have a mean which is representable as a double and also distinct from both.

  2. anonymous

    What I’m writing here might not apply in your case because there’s very little context — you don’t even mention what programming language you’re coding in (C? C++? something else?). That said:

    A word of caution might be in order. Whether your code works as expected depends on the type of floating point arithmetic that you use. If you’re on x86 e.g. and you use x87 instructions, the above might not behave as expected. The issue is explained here: https://gcc.gnu.org/wiki/x87note

    To illustrate, please consider the following piece of code:


    #include
    #include

    int
    main()
    {
    double x = 1.0;
    double y = std::nextafter(x, 2.0);
    double middle = (x+y)/2.0;
    //std::cout << middle << std::endl;
    if (x == middle or y == middle)
    std::cout << "Behaving as expected" << std::endl;
    else
    std::cout << "Help, where are we?" << std::endl;
    }

    If I compile and run that via clang++ -std=c++11 foo.cc && ./a.out, on my machine, everything’s fine. If I use clang++ -std=c++11 -m32 -mno-sse foo.cc && ./a.out instead, they’re not. Unless of course you add the line that writes middle to std::cout back in. Oh well.

    Reply
    1. anonymous

      Your blog ate my includes. HTML and C++ don’t mix. Either way, of course they’re supposed to be cmath and iostream.

  3. Pingback: Sunday Links 06/19/2016 | William Tyler Bradley

Leave a Reply to David Cancel reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">