mjhun's blog

Is floating point arithmetic deterministic?
By mjhun, 8 years ago, In English

A couple of days ago, I was trying to solve 739E - Gosha is hunting. My approach was similar than that of the editorial . My first submission (22589895) gave WA. After a while struggling to find what was wrong, I looked the case that was failing. I tested it on my computer but it gave the right answer!

After some debugging in Ideone (which gave the same answer as Codeforces), I realized that the problem was this: Somewhere in my code I insert into a set a pair<double,int> , where the double is the result of some operation (line 35).

ca.insert(mp((1-p[j].snd)*p[j].fst,j));

During execution I may move that pair to another set called wa, and somewhere else I erase some value from one of these sets (lines 62-68).

if(wa.count(mp((1-p[j].snd)*p[j].fst,j))){
	...
	wa.erase(mp((1-p[j].snd)*p[j].fst,j));
}
else {
	ca.erase(mp((1-p[j].snd)*p[j].fst,j));
}

What was happening is that it wasn't erasing when it should. Then I created an auxiliary double array kk, where I store the value before inserting it into the set, and from which I read when I want to erase it from the set. This solved the problem (submission 22590238: AC).

So, the thing is: The operation (1-p[j].snd)*p[j].fst wasn't giving the same result as before, even though it's done with the exact same values and the exact same order than before. Just to be sure, I did another submission, which (before erasing from the set) asserted that the computed value is exactly the value stored in the auxiliary array (submission 22601078: RTE, so: the assertion failed).

I thought that floating point operations are supposed to be deterministic (they should give the same result, given that they are made with the same values, in the same order and on the same platform), as they were on my computer.

It may be that I'm mistaken, that there is some other error in my code which I didn't realize, or that there is some problem with the compiler (maybe an optimization bug). I thought that probably someone here could help me understand what is going on.

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by mjhun (previous revision, new revision, compare).

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

TL,DR: Compiler works OK, but not in the way you expected.

Floating point computation is not "deterministic", at least not in the sense in which you use the word. In particular, even if you use the same piece of code in two different places, the outputs may still be different. This is because the compiler does have some freedom when generating such code. In particular, it is allowed to compute the intermediate values to a higher precision than required by your code, and this may produce values that get rounded in different directions.

Essentially, whenever you test floating-point values for exact equality, you are the one making a mistake. Always expect imprecisions when dealing with floating-point numbers. (Alternately, avoid using them if possible.)

→ Reply