Written by Swaraj
on February 22, 2018

Issues using floats as key in Maps/Sets

Let’s understand this with a simple problem?

Given a list of numbers find all unique fractions A[p]/A[q] for given p < q.

[1,2,4] => [1/2,1/4,2/4] => [0.5,0.25,0.5] => so Answer is 2.

So obvious solution is to build a set of floats and keep putting all these fractions and then return the size of set. Will this work?

Well, let’s see what the code below prints. Make a guess?

    #include <bits/stdc++.h>
    using namespace std;

    int getCount(vector<float> v) {
        set<float> s;
        for(auto a:v) s.insert(a);
        return s.size();
    }

    int main() {
        // your code goes here
        float c = 94911152;
        vector<float> v;
        v.push_back(1/c);
        v.push_back(1/(c-1));
        
        cout<<"Length of set containing all fractions: " << getCount(v) <<endl;
        
        return 0;
    }

Above code prints 1 instead of 2. Confused? Every machine has a limitation in representing a floating point number. Each machine has a machine epsilon generally denoted as eps. So for any stored floating number, the next floating point number we can represent is x(1+eps). So we are losing some precision. More Details

Let’s print the values and see why above code doesn’t work. Carefully see the output of below code. Mathematically x1 and x2 are different numbers, still we are getting same floating point as output.

    #include <iostream>
    using namespace std;
    
    int main() {
        // your code goes here
    
        float c = 94911152;
        float x1 = 1/c, x2 = (1/(c-1));
    
        printf("X1 : %.50f\n", x1);
        printf("X2 : %.50f\n", x2);
    
        return 0;
    }

X1 : 0.00000001053616927038092399016022682189941406250000
X2 : 0.00000001053616927038092399016022682189941406250000

So if we want to use A[p]/A[q] as fraction, we need to pull out some math. For any given fraction we can reduce this to its irreducible fraction representation and then use those numerator and denominator pair as key. Ex: 2/4 can be represented as 1/2. So we can store 2/4 as a pair (1,2) instead storing it as 0.5. for above example we can store x1 and x2 as 2 different numbers. (1,94911152) and (1,94911151). This is now error free. To reduce the fraction we can diving both num and den by gcd(num,den). See the code below for an idea.

    #include <bits/stdc++.h>
    using namespace std;

    int getCount(vector<pair<int,int>> v) {
        set<pair<int,int>> s;
        for(auto a:v) s.insert(a);
        return s.size();
    }

    int gcd(int a,int b) {
        if(b==0) return a;
        return gcd(b,a%b);
    }

    int main() {
        // your code goes here
        int c = 94911152;
        vector<pair<int,int>> v;
        v.push_back(make_pair(1/gcd(1,c),c/gcd(1,c)));
        v.push_back(make_pair(1/gcd(1,c-1),(c-1)/gcd(1,c-1)));
        
        cout<<"Length of set containing all fractions: " << getCount(v) <<endl;

        return 0;
    }

This idea can be applied in many problem settings.

Sample problem: Max Points in A Line

← Top