SaBuZa's blog

Strange C++ behavior
By SaBuZa, history, 8 years ago, In English

Because my friend's English is not very good, I am asking this question on his behalf.

He says on problem E of yesterday's round, he was debugging and finally got accepted but found that he could only get accepted with a debugging if statement that is supposed to be useless.

When he removes the if statement, it gets wrong answer on test case 38. However, when the if statement is included (highlighted in green in the image), it is accepted but the commands in the if statement are not even executed.

It is very confusing for me that the addition of an if statement that does nothing to change the values of any variables could change the output of the program.

The two submissions can be found here: http://codeforces.com/contest/681/submission/18481671 (Accepted with if statement) http://codeforces.com/contest/681/submission/18481662 (Wrong answer without if statement)

Does anyone have any explanation for this phenomenon?

Tags c++
  • Vote: I like it
  • +42
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by SaBuZa (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

http://stackoverflow.com/questions/6722293/why-comparing-double-and-float-leads-to-unexpected-result

In short the value of o1 variable is rounded.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    But regardless of the imprecision if it enters the if statement it should not be accepted because it would output junk and fail. If it doesn't, then removing it should get the same answer and also be accepted. My question is why does removing it change the answer.

    → Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it +54 Vote: I do not like it

Ok, wild guess. Not so wild probably, but still.

I didnt' solve this problem so I don't know how much correctness of your program depends on all those numerous double to double comparisons. If it doesn't, then my explanation doesn't apply. I do comparisons like this only if I am not interested in equality and can tolerate marginal errors.

What surprises you is how program can still behave differently? It easily can. The problem is the way compiler allocates double values to registers (and memory). Good compiler always tries to implement tight loops with use of registers only — thus achieving highest performance. Double values are stored in Floating point registers. Caveat is that in modern processors floating point registers have 80 bit precision. So if you do all your calculations within FPU registers, your calculation will have 80bit precision. The moment you take value out of FPU register it is truncated to 64 bits precision.

My guess is that variable o1 in failing submission is kept within FPU register during the whole cycle. Thus it has 80 bits precision. In accepted submission, because of that additional comparison operator (which forces compiler to cast double to boolean) compiler somehow drops this optimization and truncates o1 value to 64 bits precision. Probably on every loop. So it should also be slower, but this is not problem here.

So in two submissions the same o1 value will be slightly different. If this slight difference can cause problems to your program, then this is the most likely reason.

Solution — straight and simple — double value comparisons are evil, don't use them.

→ Reply