ekzhang's blog

Strange behavior of doubles in C++, Possible UB?
By ekzhang, history, 7 years ago, In English

I recently submitted twice to problem 865C/866C (same problem), Gotta Go Fast.

http://codeforces.com/contest/866/submission/30954904

http://codeforces.com/contest/865/submission/30956252

The first submission got wrong answer on test 1 on Codeforces. But I tested the solution both locally and on Ideone, and the answer was correct.

In the second submission my only change was adding the following one "useless" line of code to a for loop:

if (hi > 2 && hi < 1) cout << "this should never run" << endl;

It got AC.

My question is, why is this happening? I've tried debugging it locally and looking at the assembly, but there are no bugs when it runs on my local machine or on Ideone; it's only acting strangely on Codeforces. I've been staring at this code for many hours now thinking it might be undefined behavior, but I've tried many slightly different submissions (with long double, without the call to min) that work just fine without the extra useless if statement.

Tl;dr: I am utterly confused and would greatly appreciate if you could help me find where my UB is, or if there's some other problem with floating-point precision :-)

Thanks!

  • Vote: I like it
  • +28
  • Vote: I do not like it

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

I suggest starting with floating point section here.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

Seems to be optimizer precision error. With #pragma GCC optimize ("O0") it works as expected.

As I know it and can explain: registers for floating point arithmetic are larger then double, they are like a long double. So you may expect some precision errors even after simple assignment:

double x, y;
...
x = y;
...
if (x != y) {
  cout << "Sometimes it can be True. Because compiler will compare them as long double values and they may have some non zero difference as long double values." << endl;
}

I think, The best way to avoid this error is next comparison:

if (abs(T[0][0] - K) < max(K, T[0][0]) * 1e-15)
→ Reply