5amia's blog

Problem with GNU C++17 Compiler
By 5amia, history, 3 years ago, In English

I tried to solve Round 340 — Problem A

same code gives WA in GNU C++17 Compiler but is accepted in both the c++14 and c++20(64) compilers.

AC Submission (c++20)

AC Submission (c++14)

WA Submission (c++17)

I expected ceil(5*0.2) to be 1, but it's giving 2. What's causing this?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it -10 Vote: I do not like it

First of all, when you're dealing with doubles presession problems occur a lot. Each compiler has its way of representing the numbers.

So if you can turn your problem from double domain to integer doman, you will avoid these problems.

Nice tricks that might help you:

Suppose that you have 2 Integer numbers a, b and you need to do the following operations:


1- Ceil(a/b)   = (a+b-1)/b   => Just write it in C++ as it is
2- Floor(a, b) = a/b         => This's the default C++ division behavior (make floor)

So you can now refer to my solution I did the same a, b will be the given n, 5

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

    Please, don't write text where all words have their first letters capitalized. It looks awful.

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

Because of precisions errors in doubles in c++, 5 * 0.2 may have evaluated to something like 1.000000000000000000002, which though very insignificantly, is greater than 1. So, when you apply ceil function on the number, it outputs 2.

To counter this problem, you can substract a very small number (say 10^-9) from the output. If the output is slightly greater than actual result, it would come down and give correct output. If it slight lesser, let's say 0.999999999999999999998, it won't go below the whole integer, and still give correct output.

(Note that we are subtracting because of the way that ceil function works. To repeat the same thing using floor function, you'd need to add the very small value.)

PS: If you're just doing ceil division, use the formula (a + b — 1) / b for evaluating ceil(a / b) as stated in above comment. This formula keeps all the calculation in integers, avoiding the precision errors.

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Floating point numbers work in mysterious ways in 32 bit mode (meaing your C++14 and C++17 submissions). I've previously written a blog all about it here https://mirror.codeforces.com/blog/entry/78161 .

As an example, take a look at these two submissions in C++17:

AC 222471341

WA 222471378.

These two submissions do the exact same calculations, but one gets AC and the other WA. The reasons for this is explained in detail in my blog. But the short story is that it has to do with 32 bit C++ sometimes sneakily doing calculations using long doubles, even if you tell it to use doubles. It happens to be the case using long double leads to WA 222472878.

My recommendation is that if you are going to use floating point numbers, then try to avoid using 32 bit C++. Instead submit in C++20(64 bit). Back when Codeforces only had 32 bit C++, Codeforces used to be filled with blogs like this one talking about weird bugs concerning floating point numbers. These kind of blogs are a lot less common nowdays since now most people submit in 64 bit C++.

→ Reply