Nonsense about doubles

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

DP Bitmask - Topic Stream

Shayan

До начала 03:22:34

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Nonsense about doubles

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

I got wrong answer with this solution:

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

And i got accepted with this solution:

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

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

Bera
9 лет назад
23

Комментарии (23)

Написать комментарий?

HellKitsune

9 лет назад, # |

+40

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.net/contest/568/submission/12457494

→ Ответить

Bera

9 лет назад, # |

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

→ Ответить

Zzyzx

9 лет назад, # ^ |

+35

That's what unpredictable means.

→ Ответить

Bera

9 лет назад, # ^ |

I think it's so stupid.

→ Ответить

misof

9 лет назад, # ^ |

+56

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.

→ Ответить

dalex

9 лет назад, # ^ |

-9

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.

→ Ответить

HellKitsune

9 лет назад, # ^ |

+23

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

→ Ответить

andreyv

9 лет назад, # ^ |

+19

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

→ Ответить

dalex

9 лет назад, # ^ |

-43

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?

→ Ответить

andreyv

9 лет назад, # ^ |

+11

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.

→ Ответить

misof

9 лет назад, # ^ |

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.)

→ Ответить

Bera

9 лет назад, # ^ |

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.net/contest/500/submission/9326220

When i used double it passed:

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

→ Ответить

dalex

9 лет назад, # ^ |

← Rev. 2 →

-14

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

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".

→ Ответить

Xellos

9 лет назад, # ^ |

← Rev. 4 →

+19

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):

You don't like how C++ compiler/s handle this? Make your own and make it popular.
Deal with it; it doesn't negatively affect your life and there are reasons for it.

→ Ответить