Блог пользователя Dardy

Автор Dardy, история, 6 лет назад, По-английски

Me and MrOkasha found an odd quirk with the GNU G++ compiler, (we tested with G++11, G++14, and G++17, all having the same bug).

This code here:


#include <bits/stdc++.h>
using namespace std;

set<double> st;

int main() {

    double x, y;
    for(int i = 0; i < 3; ++i){
        cin >> x >> y;
        st.insert(y/x);
    }
    cout << st.size() << endl;
}
// input:    5 -2 5 -2 5 -2

should output without any doubt '1', as the set should remove duplicate numbers. The output is 3 for some reason on the GNU compilers. It should be noted that the output is indeed 1 on Clang++17 compiler, Visual C++, and other available versions of GNU G++ compilers found online, for us, it seems the bug only occurs here on codeforces, verified by the Custom Invocation feature.

The weirdest thing about this bug is that, for some bizarre reason, if the declaration of the set set<double> is moved to inside the main function, the code works as intended.

Any thoughts on this weird issue?

  • Проголосовать: нравится
  • +39
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +78 Проголосовать: не нравится

Welcome to the world of the floating point arithmetic!

The compiler is allowed to do floating point operations sometimes with higher precision than necessary. It is also allowed to do the exact same floating point operations with just the precision that was necessary at other times. Therefore the exact same operation may produce slightly different results, which is what you see here.

So it's not a bug.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I'm not entirely convinced because of multiple reasons, why specifically does it not work when the set is global not local, and does it produce slightly different results every single time?

    Also, what compiler options/flags do I need to reproduce this on my own machine? Why does this issue only occur on codeforces' machine?

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      I guess -mfpmath=387 should be such a flag. And you need x86 machine or 32-bit building mode, -m32 for example.

      The answer on your first question is may be the fact that nowadays most of the floating-point arithmetic is performed by SSE instructions, and not by FPU (math coprocessor). CF servers may be an exception =) And SSE has no such problems.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Isn't -5/2 calculated without precision loss in any floating point type?

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      As I know it works in the following way: you have 8 byte variables, but math coprocessor operates with 10 bytes registers, so you get 2 bytes (actually not) from garbage for most of operations performed by math coprocessor (not only /, but < also). Btw, it's -2/5.

      And it still weird that it depends on if the set is global. So I actually can be wrong, and it's really a bug of GCC (not first time for it). If someone isn't lazy and can take a look at the difference of compiler output for x86 mingw, we will know the answer for sure =)

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится
What you should use in double comparison

Link to cppref

P.S. You can change epsilon when you will need to calculate many sqrt, sin, cos, tan, atan

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +47 Проголосовать: не нравится

    This is not a good compare function. It doesn't satisfy the requirement that a function is a strict weak ordering:

    if comp(a,b)==true and comp(b,c)==true then comp(a,c)==true

    For your function, I can find a,b,c such that isEqual(a,b) and isEqual(b,c) but not isEqual(a,c)

    See this code
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Always use customized rational data type when you have to compare rational numbers!

I lost a gold medal in 2018 ICPC Xi'an Invitation because I believed I could mitigate the percision issue with double and some stupid adjustment.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Never hash floating numbers! Instead you can use this

Spoiler