How to deal with precision in C#

Question

Bizarre precision behavior in finding the number of integral points between two points exclusive:

I was writing an algorithm for this which went like this (pseudo).

Given x1,y1 and x2, y2

I calculated double m where m is the gradient of the line segment given as (double)(y2-y1)/(x2-x1) then I calculated double c where c is the y intercept given as y1 - (m*x1)

then for i = Min(x1,x2) i < Max(x1,x2) for j = Min(y1, y2) j < Max(y1,y2) if j = (m*i) + c then ++

finally, return the result -1

The code works for some test cases but fails on others for instance when the two endpoints are perpendicular to each other I had to deal with infinity for m, and NaN cases for c. But, one particular case caught my eye, Test case 43,38,17,6 for x1,y1 and x2, y2 respectively.

running the code j starts at 6 and i at 17 so this point is definitely on the line segment even though I shouldn't be counting it because it is an end-point. What's bizarre is for this value i, j != (m*i)+c = 5.9999999999... instead of 6. how is that possible? where am I losing precision for this? More importantly how i'm I losing precision?

code:

        int cnt = 0;
        double i, j;
        double m = (double)(y2 - y1) / (x2 - x1);
        double c = y1 - (m * x1);
        for (i = Math.Min(x1, x2); i <= Math.Max(x1, x2); i++)
        {
            for (j = Math.Min(y1, y2); j <= Math.Max(y1, y2); j++)
            {
                if (j == (m * i) + c||double.IsInfinity(m) && double.IsNaN(c))
                    cnt++;
            }
        }
        return cnt - 2;

So I changed all my variables to decimal but unfortunately, I still get failed test cases. But I think i've narrowed it down to this point here :decimal m = (decimal)(y2 - y1) / (x2 - x1);

Answer 1

Doubles cannot be precise. They are only precise up to a certain number of digits. Remember they use an internal format to be stored in bytes. This will inevitable cause some precision error.

And even worse, some values you put into a double are unable to be precisely stored, even with no calculation made.

Example to make you aware: Assigning 1.94 to a double variable can be tested here and will result in: 1.939999999999999946709294817992486059665679931640625!

Its bad practice and doomed to fail to compare two floating point numbers with equality operator.

Important read about floating point numbers: What Every Computer Scientist Should Know About Floating-Point Arithmetic

Squeezing infinitely many real numbers into a finite number of bits requires an approximate representation. Although there are infinitely many integers, in most programs the result of integer computations can be stored in 32 bits. In contrast, given any fixed number of bits, most calculations with real numbers will produce quantities that cannot be exactly represented using that many bits. Therefore the result of a floating-point calculation must often be rounded in order to fit back into its finite representation. This rounding error is the characteristic feature of floating-point computation.

As solution if you really want to compare you can sensitively round the results with Math.round(x, decimals) before comparing them.

Answer 2

m and c are doubles, so (m*i)+c is going to return a double. j however, is an int. So you're comparing an integer to a double. Given floating point representation, this is going to be an issue SOMEWHERE when doing direct comparisons. You need to either cast the right-hand side of that comparison as an integer, or do some sort of non-exact comparison. Alternatively you could use something that is not floating point precision, like decimal, which won't show this issue.