What's the difference between those statements?

Question

These days, I'm working on some problems regarding ACM-ICPC (although I already graduated.. just for fun..). Yesterday, I nearly became crazy because there is an online judge which always said "WRONG ANSWER" to code I'd written. And finally after more than horrible 10 hours, I realized that a following statement was the reason.

   int target = (int)((double)(M * 100) / N) + 1;          // RIGHT!!
   int target = (int)((double) M / N * 100) + 1;            // WRONG!!

I couldn't exactly know how and why the first statement behaves differently from the second one. Because I'm not allowed to see test cases which are used by the judge, it's a little hard for me to understand when the code can go wrong. Is there anybody who can explain to me? Thank you.

       * I'm using Java.

Answer 1

As far as I can tell, the result of these two expressions

(double)(M * 100) / N
(double) M / N * 100

is the same EXCEPT for floating point precision errors (and also for possible overflows, but let us ignore them here since both lines are susceptible to them, albeit in a different way). These errors COULD cause the values to be one slightly above or equal to an integer, and one slightly below the same integer, which would cause

(int)((double)(M * 100) / N)
(int)((double) M / N * 100)

to differ by one. In general, when dealing with floating point, you have more chances to get closer to the "real" value if you leave the division as the last operation.

There is one further consideration, which can get quite tricky: you have no parentheses around (double)M/N in your second line. This MIGHT give additional freedom to an optimizer, which could make the result dependent on the optimization level. I don't know whether this can happen in Java.

As for the order of operations, I tried out this particular case in C (because that's quicker for me):

int i, j, k;
for (i = 1; i <= 100; i++) {
   j = (int)(((double)i / 100) * 100);
   if (i != j) {
      printf("%d -> %d\n", i, j);
   }
   k = (int)(((double)i * 100) / 100);
   if (i != k) {
      printf("%d ?? %d\n", i, k);
   }
}

and the output on my machine is

29 -> 28
57 -> 56
58 -> 57

Replacing 100 with 10000000 yields 587200 lines of the same kind (i.e., an error rate of 5.872%)