Why is this loop endless only when I am not debugging it?

Question

Below program does some computations to compute how many terms of some infinite converging sum are needed to exceed a certain threshold. I understand/suspect that loops like this may not terminate if rate is too large (e.g. 750, see below) because of computation inaccuracies caused by floating point arithmatic.

However, below loop outputs i=514 in debug mode (microsoft visual studio .net 4.6.1), but does not terminate ("hangs") in release mode. Perhaps even more strange: If I out-comment the "if" part inside the loop (meant to figure out what is happening), then the release mode code suddenly also outputs i=514.

What are the reasons behind this? How to avoid problems like this from popping up in release mode? (Edit: I would rather not add an if statement or break statement in production code; this code should be as performant as possible.)

 static void Main(string[] args)
    {     
   double rate = 750;
        double d = 0.2;
        double rnd = d * Math.Exp(rate);
        int i = 0;
        int j = 0;
        double term = 1.0;
        do
        {
            rnd -= term;
            term *= rate;
            term /= ++i;
            //if (j++ > 1000000)
            //{
            //    Console.WriteLine(d + " " + rate + "  " + term);
            //    j = 0;
            //    Console.ReadLine();
            //}
        } while (rnd > 0);             
        Console.WriteLine("i= "+i);//do something with i
        Console.ReadLine();
        return;
 }

Answer 1

Executive Summary Your code is broken even in Debug - it produces the wrong result even when the loop exits. You need to be aware of the limits of floating-point arithmetic.

If you step through your code with a debugger, you quickly see what's wrong.

Math.Exp(rate) is large. Very large. Larger than a double-precision number can hold. Therefore rnd starts off with the value Infinity.

When you come to rnd -= term, that's Infinity minus some number, which is still Infinity. Therefore rnd > 0 is always true, as Infinity is greater than zero.

This carries on until term also reaches Infinity. Then rnd -= term becomes Infinity - Infinity, which is NaN. Anything compared to NaN is false, so rnd > 0 is suddenly false, and your loop exits.

I don't know why this changes in release mode (I can't reproduce it), but it's entirely possible that the order of your floating-point operations was changed. This can have drastic affects on the output if you're dealing with both large and small numbers at the same time. For example, term *= rate; term /= ++i might be ordered such that term * rate always happens first in Debug, and that multiplication reaches Infinity before the division happens. In Release, that might be re-ordered such that rate / ++i happens first, and that stops you from ever hitting Infinity. Because you started off with the error that rnd is always Infinity, your loop can only break when term is also Infinity.

I suspect it may depend on factors such as your processor, as well.

EDIT: See This answer by @HansPassant for a much better explanation.

So again, while the difference between hanging and not hanging may depend on Debug vs Release, your code never worked in the first place. Even in Debug, it produces the wrong result!

If you're dealing with large or small numbers, you need to be careful about the limits of double precision. Floating-point numbers are complex beasts, and have lots of subtle behaviour. You need to be aware of that, see for example this famous article: What Every Computer Scientist Should Know About Floating-Point Arithmetic. Be aware of the limits, the issues with combining large and small numbers, etc.

If you're working near the limits of floating-point, you need to test your assumptions: make sure that you're not dealing with numbers which are too large or too small, for example. If you expect an exponentiation to be less than Infinity, test that. If you expect a loop to exit, add a guard condition to make sure it exits with an error after a certain number of iterations. Test your code! Make sure that it behaves correctly in the edge cases.

Also, use a big number library where appropriate. If possible, rework your algorithm to be more computer-friendly. Many algorithms are written such that they're elegant for mathematicians to write in a textbook, but they're impractical for a processor to execute. There are often versions which do the same things, but are more computer-friendly.

I would rather not add an if statement or break statement in production code; this code should be as performant as possible.)

Don't be afraid of a single if statement in a loop. If it always produces the same result -- e.g. your break is never hit -- the branch predictor very quickly catches on and the branch has almost no cost. It's a loop with a branch which is unpredictable that you need to be careful of.