Atomsky's blog

C++17 Undefined Behavior
By Atomsky, history, 4 years ago, In English

In CF Round #727 (Div. 2), I submitted 120147862 for Problem-C: Stable Groups. It gave a wrong result on test 62 in GNU C++17. When I submitted the same code in GNU C++11, it was accepted (120149347).

I tried to figure out what went wrong in C++17. If I simply add a line that prints out the array output after line 14, like cout << foo[i] << endl;, the code gives the correct result in C++17. I am having trouble understanding why this might happen! What can I do in such cases?

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

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

It's probably the fact that you are using doubles, and (I heard that) doubles in C++11 and C++17 work differently

instead of

ceil((jar[i] - jar[i-1])/(double)x);

you can try

(jar[i] - jar[i - 1] + (x - 1)) / x;

this will avoid working with doubles, as ceil(a / b) can be equivalent to (a + b - 1) / b

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

Dont use ceil because 2+eps might be ceilied to 3. As a rule of thumb avoid floats when you can in CP. It is not UB, mingw 32bit is configured to use excess precision by default it means that it will do all the operations in 80 bit float or sth like that. 64 bit one isn't it seems.

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

I have fallen into this trap at least twice. For a rational number $$$r=\frac pq$$$, when you want to calculate $$$\left\lceil\frac pq\right\rceil$$$, don't use ceil(1.0 * p / q) (which can cause serious accuracy errors when $$$p$$$ and $$$q$$$ are very large), but use (p + q - 1) / q instead. Note that some changes need to be made when $$$p,q$$$ is negative, because in C++ signed integer division truncates towards zero. You can read this post for more information.

→ Reply