kien_coi_1997's blog

Why can this code work strangely?
By kien_coi_1997, 10 years ago, In English

The following code is simple, but it makes different outputs on different machine.

I knew that the reason of this strange behaviour is related to floating-point accuracy. But I can't find any considerable reasons.

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 200005;
int n, x[N], y[N];
pair<double, double> a[N];

main() {
    scanf("%d", &n);
    for (int i=1; i<=n; i++) {
        scanf("%d%d", &x[i], &y[i]);
        a[i] = make_pair(1.0/x[i], 1.0/y[i]);
    }
    sort(a+1, a+n+1);
    
    for (int i=1; i<=n; i++)
    if (binary_search(a+1, a+n+1, make_pair(1.0/x[i], 1.0/y[i])))
    printf("%d ", i);
    cout << endl;
}

Input

3
1 3
2 2
3 1

Output on my computer (expected output)

1 2 3

Output on Codeforces

2

Can you show me the reason?

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

Comments Comments (10)
| Write comment?
»
10 years ago, # |
  Vote: I like it -101 Vote: I do not like it

Use Visual Studio :)

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

Next code:

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 200005;
int n, x[N], y[N];
pair<double, double> a[N];

int main() {
    scanf("%d", &n);
    for (int i=1; i<=n; i++) {
        scanf("%d%d", &x[i], &y[i]);
        a[i] = make_pair(1.0/x[i], 1.0/y[i]);
    }
    sort(a+1, a+n+1);
    
    for (int i=1; i<=n; i++){
        printf("%0.18f %0.18f\n", 1.0/x[i], a[i].first);
        if (!(1.0/x[i] < a[i].first) && !(a[i].first < 1.0/x[i]))
            printf("%d \n", i);
        if(1.0/x[i] < a[i].first) printf("Fail type one on %d: 1.0/x[i] < a[i].first\n", i);
        if(a[i].first < 1.0/x[i]) printf("Fail type two on %d: a[i].first < 1.0/x[i]\n", i);
    }
    cout << endl;
}

on test

3
3 1
2 2
1 3

Output on Codeforces:

0.333333333333333310 0.333333333333333310
Fail type two on 1: a[i].first < 1.0/x[i]
0.500000000000000000 0.500000000000000000
2 
1.000000000000000000 1.000000000000000000
3

I don't know why it happens, but may be the cause of issue in pair<double, double>.

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

You shouldn't normally expect doubles to be equal

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +22 Vote: I do not like it

    The safest way is not always the best way. In some case, using epsilon is very complex, for example, map<double, int>.

    Therefore, I want to know as many floating-point guarantees as possible.

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

You should write your own Comparator with eps margin precision.

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

    And you should put WARNING: FOR COMPETITIVE PROGRAMMING ONLY disclaimer.

    Or do you know at least one epsilon-based transitive comparator?

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

      Any epsilon-based comparator is transitive for some subset of numbers...

      If you decided to use epsilon-based comparator, you most probably have confidence that it is transitive for subset it will be used on.

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

        or you just decided to use 1e-9 because you don't want to think

        → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +48 Vote: I do not like it

Solution: use -ffloat-store flag.

Short explanation: "Intel x86 processors use 80-bit extended precision internally, whereas double is normally 64-bit wide."

Long explanation: http://stackoverflow.com/questions/7517588/different-floating-point-result-with-optimization-enabled-compiler-bug.

Anyway, for competitive programming, use epsilon to compare two floating-point numbers.

→ Reply