Bera's blog

Nonsense about doubles
By Bera, history, 9 years ago, In English

I got wrong answer with this solution:

http://codeforces.me/contest/568/submission/12456152

And i got accepted with this solution:

http://codeforces.me/contest/568/submission/12456422

I think both of them should get accepted. Can someone help me?

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

»
9 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Well, comparing doubles like this leads to unpredictable results. Use integers whenever possible, and when not, use epsilon when comparing two doubles (or comparing double with integer).

http://codeforces.me/contest/568/submission/12457494

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I know but i just changed the char string into a string. I didn't change anything about doubles and it got accepted. Why?

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

    That's what unpredictable means.

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

      I think it's so stupid.

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

        Thinking so will not help you in the future. Instead, you should try to understand why floating-point numbers work the way they do (there are good reasons), and how they should actually be used.

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

          So why do they work this way? Do you agree that in both cases the bits stored in these double variables are the same? And if the bits are the same, any operations must produce the same result, right? What am I missing? Don't tell me this logic is wrong.

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

            You'd think that even though there are precision errors, doing the same thing should lead to the same results, but there's also top answer here: link

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

            Why is cos(x) != cos(y) even though x == y?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it -43 Vote: I do not like it

              Okay, got it, so instructions generated by compiler do different things from what the source code says. One more question: why this shit is turned on?

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

                The very first sentence from the article above:

                Floating point arithmetic simply does not work like most people expect.

                You expect it to produce exact results, while it only produces approximate results.

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

                No, you did not "get it". The instructions generated by the compiler do exactly what the source says. The problem here is that you are reading the source incorrectly.

                More precisely, you are making assumptions you should not make, such as "==(double,double) is a test whether two real numbers are equal".

                Do read the article andreyv posted, including the previous two questions before the one with the cosines.

                The big picture here is that the IEEE standard for floating-point numbers was designed to be platform-independent. This is necessary, because there have been, and to some extent there still are, wild differences between different platforms. The main thing the standard gives you are guarantees on the least amount of precision that will be used to perform your calculations. E.g., if you use a "double" anywhere in your code, you have the guarantee that all calculations with that value will be done with at least the 53 most significant bits of the number. The computer is allowed to use more precision whenever it's available, and that (along with rounding errors) is one of the sources of all this confusion.

                All of this is actually a good thing: it allows the compilers to optimize your code better and to make it run faster, and it also makes well-written code portable to different architectures.

                There are some niche cases (way more frequent in competitive programming than in "real life") where you don't want the default floating-point behavior. In those cases, you always have the option to avoid using them, and to replace them by your own implementation that is exact.

                That is also a good advice for competitive programming. You can certainly use doubles in many tasks, if you really know what you are doing. But if you don't, it's much safer to avoid them and use integers only. (Integers can be used, for example, to represent exact fractions, and also to represent fixed-point arithmetic -- e.g., if the input are numbers like "$0.47", just count everything in cents instead of dollars.)

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

                  You are right, but it is hard to decide because

                  I used long long integer to avoid double problems but it got wrong answer because of overflow:

                  http://codeforces.me/contest/500/submission/9326220

                  When i used double it passed:

                  http://codeforces.me/contest/500/submission/9326317

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 years ago, # ^ |
                  ← Rev. 2   Vote: I like it -14 Vote: I do not like it

                  ================================================

                  More precisely, you are making assumptions you should not make, such as "==(double,double) is a test whether two real numbers are equal"

                  Very nice, so I should make an assumption "==(double,double) is a test whether (two real numbers are equal) and (the moon is in its certain phase)", right? Even if they are the return values of the same function called with the same arguments? And have the same binary representation (I'm not talking about NaN-s)? Don't you find it illogical?

                  In the example with cosines, I read the code cos(x) == cos(y) as "Calculate cos(x) as double (the function returns double, so I expect the result to be double), then calculate cos(y) as double, then compare them", and it's the meaning everyone would think, probably except C++ compiler authors, who understand it as "calculate cos(x), store it as double, then calculate cos(y) as 80-bit number (WTF?), then compare them".

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 years ago, # ^ |
                  ← Rev. 4   Vote: I like it +19 Vote: I do not like it

                  Why would you ever want to assume doubles can be precise? It'll screw you over sometimes and you can always replace equality checking by abs() < eps checking.

                  Don't you find it illogical?

                  With sufficient lack of background knowledge, anything can seem illogical. In this case, if you know what the code appears to do, but not what it's translated to on compile time, then it will seem illogical — until you realise that equality checking in general has little meaning with doubles for unrelated reasons, anyway. Garbage in, garbage out.

                  The way I see it, you have 2 options (not counting throwing a tantrum):

                  1. You don't like how C++ compiler/s handle this? Make your own and make it popular.

                  2. Deal with it; it doesn't negatively affect your life and there are reasons for it.

                  → Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Thanks anyway.

→ Reply
»
9 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Твое решение не принято потому что неправильный ответ на тест 4 9. А второе принято потому что все правильные ответы

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

    I tried the case 4 9 in g++ and it gives the right answer. You can try it too if you want.

    → Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Bera, in your code you use long long int. Where is different long long or long long int... int or long in C++?

Thanks for advice.

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

    There is no difference between long long and long long int. I wrote int then i realized that i should use long long and i added long long.

    → Reply
»
9 years ago, # |
  Vote: I like it -26 Vote: I do not like it

I cannot help you. So go away.

→ Reply