Spot the defect: rounding

The intention of this method is to round a double to the nearest integer. If the double is exactly half way between two integers then it rounds to the larger of the two possibilities:[1. For negative numbers, -1.5 should round to -1.0, since -1.0 is larger than -2.0; I do not mean larger in the sense of absolute magnitude. That would be characterized as “midpoint rounding away from zero”.]

static double MyRound(double d)
{
  return Math.Floor(d + 0.5);
}

Is it correct? Can you find a value for which it does not give the mathematically correct value?[2. HINT: The value I’m thinking of is small.]

UPDATE: The answer is in the comments, so if you don’t want spoilers, don’t read the comments.

Next time on FAIC: The answer, of course.

Advertisements

32 thoughts on “Spot the defect: rounding

  1. 0.5 – (some number close to machine epsilon, don’t know the terminology)

    var machineEpsilon = 1.0;
    while (1.0 + machineEpsilon > 1)
    machineEpsilon /= 2;

    MyRound(0.5 – machineEpsilon / 2) returns 1;

  2. Any number in between 0.5 and 0.49999999999999999 (which is 0.5 – 1e-17) results in 1 instead of 0. The same for 0.5 – double.Epsilon

    • var x = 0.5 – double.Epsilon;
      if (x == 0.5)
      Console.WriteLine(“Huh? What’s going on here?”);

  3. The number is 0.5 – ε/4, aka. the largest floating-point number strictly less than 0.5. Explanation: ε/4 is the unit of the last place of numbers between 0.25 (inclusive) and 0.5 (exclusive). When you add 0.5 to 0.5 – ε/4, you get 1.0 – ε/4 in exact arithmetic. However, this number has too many bits. The last bit is a 1, so round-to-even means the number as a whole is rounded to 1. The function returns 1, which is not correct.

  4. In my opinion this question is pointless in practice. Floating point numbers should not be used for exact calculations because they do not represent exact numbers. So if the number passed as argument is not exact by definition then how do we know that the rounding is not correct?

    • I totally agree; in practice we’re making a decision based on one part in two to the fifty-something, which is an absurdly small quantity. The exercise here is simply encouraging people to think about how floating point math differs from regular math in subtle ways.

    • In that post, they demonstrate a more extreme bug wherein myround(8388609.0f) returns 8388610.0f . This does not happen in the article’s code, though.

      • Only because this code works with a double. You can definitely construct an value that it does happen with. Try 4503599627370497. This value happens to be 0x10000000000001, the second value to require 53 bits to represent, just as the one given on that page is 0x800001, the second value to require 24 bits to represent.

  5. There are other problematic values, e.g.
    MyRound (-163840000000001.5) == -163840000000001.0
    Of course the source of the problem is the same.

    • There are still other problematic values. I was wondering about the other end of the spectrum, where consecutive double values are whole numbers.

      MyRound(4503599627370497)

      returns 4503599627370498.

      This is a problem for all odd numbers from 4503599627370497 up to 9007199254740991 (note, I only checked 3 of them).

  6. A related question to this: are there any values of `float` where `float.Parse` will yield a value which is not the closest possible `float` value to the mathematically-correct one [i.e. there is some other `float` value which isn’t merely tied with `float.Parse`, but is actually closer]? Indeed there are, and for similar reasons to the “rounding” error here. The `float.Parse` method works by converting the input string to `double` and then rounding that. An input value which, before rounded to fit a `double`, might be closer to one `float` value than another, but after rounding to `double` would be equidistant, so the succeeding round to `float` might not pick the value that was closest to the original.

  7. ‘If the double is exactly half way between two integers then it rounds to the larger of the two possibilities’. Surely, that means, …rounds to the larger by the absoulte value?’ As far as I remember, Math.Floor() will round, say, -7.64 to -8, which is smaller, not larger.

    • The .NET definition of epsilon is strange. Most other systems define it as the smallest number where 1+ϵ != 1, instead – which is, needless to say, a much larger number – 2^-52 for double.

      • 2^52, the value many languages define DBL_EPSILON as, is not quite “the smallest number where 1+ϵ != 1”, not in the default round-to-nearest mode anyway.

        What these languages define DBL_EPSILON as is the difference between the smallest double strictly above 1.0 and 1.0.

        There is a factor of nearly 2 between the two.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s