Comparing doubles using '=='

Question

I wrote the binary search code below:

class Solution {
public:
    bool check(vector<int>& dist, double hour, int mid) {
        if(mid==0) return false;
        
        double sum=0.0;
        for(int i=0; i<dist.size()-1; i++)
            sum+=ceil((double)dist[i]/mid);
        sum+=(double)dist.back()/mid;
        
        return sum<=hour ? true : false;
        // sum+=0.001f;
        // return sum<hour || std::fabs(hour-sum)<=0.001f ? true : false;
    }
    
    int minSpeedOnTime(vector<int>& dist, double hour) {
        int l=0, r=10000001;
        
        while(l<r) {
            int mid=l+(r-l)/2;
            if(check(dist, hour, mid)) {
                r=mid;
            } else l=mid+1;
        }
        
        return r==10000001 ? -1 : r;
    }
};

It works and gets "accepted", but I had few questions:

a. Is the statement return sum<=hour ? true : false; correct? I am unsure because both sum and hour are doubles. Shouldn't we be using some 'epsilon' for '==' comparison, like discussed here?
b. If uncommented, the following statement:

return sum<hour || std::fabs(hour-sum)<=0.001f ? true : false;

yields an incorrect answer. Why? The problem statement says that "hour will have at most two digits after decimal". So why does it give a wrong answer?
c. It gets accepted, if I add 0.001f:

sum+=0.001f;
return sum<hour || std::fabs(hour-sum)<=0.001f ? true : false;

Again, why?
Edit: Even std::fabs(hour-sum)==0.001f above doesn't get accepted.

Edit2: The problem statement is here, but I am not asking about the solution, etc., so I have not posted it in the question.

You're *already* not comparing with `==` but with `<=`, so any perceived problem with `==` doesn't apply. — EOF, May 26 '21 at 22:44
@EOF `f1 <= f2` is the same as `f1 < f2 || f1 == f2` and if the epsilon is symmetric then `f1` could be slightly greater than `f2` and should still test equal. So the problem with `==` does apply. — Richard Critten, May 26 '21 at 22:47
@Someone have a read of https://stackoverflow.com/questions/588004/is-floating-point-math-broken — Richard Critten, May 26 '21 at 22:49
two significant digits does not imply that adding `0.001f` would not change the result. Significant digits of `double x = 0.009` are `0.00` but significant digits of `x + 0.001f` are `0.01` — 463035818_is_not_an_ai, May 26 '21 at 23:07
@463035818_is_not_a_number, could you please elaborate? Also, please note that it gives correct answer on adding `0.001f`. — Someone, May 26 '21 at 23:15
The other potential problem with `double` is that it could be NaN, or +Inf, or -Inf. If the data set doesn't contain those, then problem avoided. Otherwise some consideration for how those are to be handled. — Eljay, May 27 '21 at 01:33
`0.009` is one example of adding `0.001f` changing the significant digits, which can make the difference between correct and not correct results here. Thats all I was saying. Your assumption that you can add `0.001f` because only two digits matter is not correct — 463035818_is_not_an_ai, May 27 '21 at 10:44
@Eljay, that's a good point. The problem statement does say: `1 <= hour <= 10^9`, so `NaN`, `+Inf` and `-Inf` are avoided. — Someone, May 27 '21 at 13:45

chux - Reinstate Monica · Answer 1 · 2021-05-27T02:26:08.397

1

Comparing doubles using '=='

This is a case where floating point should not even be used or at least greatly reduced.

Example with nary a rounding issue.

bool check(vector<int>& dist, double hour, int mid) {
    long long sum_times_mid = dist.back();
    for(int i=0; i<dist.size()-1; i++) {
        sum_times_mid += dist[i];
    }
    return sum_times_mid <= hour*mid;  // Only FP code here
}

edited May 27 '21 at 02:26

answered May 27 '21 at 02:23

chux - Reinstate Monica

143,097
13
135
256

Good writing with a broad vocabulary is a narrow slice of what is penned -- but there is hope. Fully explained in six words. Well played ... again. – David C. Rankin May 27 '21 at 04:56
Thanks. My understanding is that `long long` is an integer type, so what makes comparing with `hour*mid` (a double?) valid? Besides, if both are double (via typecasting), then would we get the right answer when `sum_times_mid==hour*mid`? Also, I submitted with your `check()` but got a wrong answer for this test case: `[1,1,100000] 2.01`. Output is: `49753` while Expected is: `10000000`. – Someone May 27 '21 at 13:40
Is it just me, or is this the most convoluted way to write `auto sum_times_mid = std::accumulate(dist.cbegin(), dist.cend(), long long(0));`? – EOF May 27 '21 at 15:34

Comparing doubles using '=='

1 Answers1