yud08's blog

Mysterious behaviour of the sqrt() function
By yud08, history, 3 months ago, In English

So I was trying to blitz my way through ABC in the last Div 2 as per usual, when, shockingly, I received the verdict "Wrong answer on test 8" for B(actually, a quite regular occurrence). I just thought it was an issue with the sqrt() function, so I coded a binary search version for the sqrt and moved on. However, after the contest, I resubmitted in C++17(I was using C++20), and it somehow passes? Also, when prompted by my friend, I added #pragma GCC target("avx2") to that submission, and it somehow failed again. Could someone please explain what's happening here?

Failing submission(C++20)
Accepted submission(C++17)
Failing submission(with pragma)

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

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

had the same issue, will just never trust floating point math again lol

→ Reply
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Use sqrtl for long long i use it for your first falling submission and got AC

→ Reply
»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

It's basically just a rounding error. C++20 believes for some reason that sqrt(854258780613619262) = 924261208, even though 924261208 * 924261208 = 854258780613619264 (the difference is only two). Here are the two submissions which I used to debug that. However, after checking the value of sqrt(854258780613619262) in a separate submission under C++17, it also prints out the wrong value, which makes even less sense.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
        cout << (ll)sqrt(854258780613619262) << endl; // Outputs: 924261208
    cout << (ll)sqrtl(854258780613619262) << endl; // Outputs: 924261207

    sqrt() sometimes fails to sqareRoot long long values. Use sqrtl() instead.

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

      That's not the question that OP asks in the blog. I think that at this point we all know that using sqrtl is more reliable than using sqrt. What I (and the OP) would like to know is the reason why this behaviour occurs exactly, why C++17 sometimes produces the correct result and sometimes doesn't, what is happening behind the scenes of all of this.

      → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    which makes even less sense.

    Floating point numbers in 32 bit C++ are really weird. Take this code for example. There is a way to make this function return True (assuming you submit using C++17):

    bool f() {
    double x;
    cin >> x;
    
    double y = x + 1.0;
    if (y >= 1.0)
        return false;
    
    pow(y, 2);
    
    if (y < 1.0)
        return false;
    return y == 1.0;
}

    At first glance this should seem completely absurd. I claim that it is possible to somehow make y be < 1.0, >= 1.0 and == 1.0 all at the same time.

    Spoilers
    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the problem is with floating point. Therefore, I used $$$n=i^2+x$$$, where $$$x \le 2k+1$$$, for each $$$\lfloor\sqrt{k}\rfloor\le i\le k$$$ until I get the minimum. And it indeed worked. So, I think the problem is with floating points.

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I too have encountered the same. And that's the reason I've permanently stuck to using C++ 17.

In the B problem of this contest, I just used floor(sqrt(num)) in C++ 17 and it worked fine for me.

→ Reply
»
3 months ago, # |
  Vote: I like it +21 Vote: I do not like it

sqrt usually has lots of precision issues and unpredictable behavior. In general, for solving $$$\lfloor \sqrt{N} \rfloor$$$ you can use this reliably:

ll sq = (ll)sqrtl(N+5);
while (sq*sq > N) sq--;
→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain why (N+5) and not a value less than 5?

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

      I don't think the value matters too much, I've seen people use 2 as a constant, and tourist's solution for B uses 10. For large values of $$$N$$$ the constant shouldnt affect the runtime much, the point is just to slightly raise the output enough to avoid situations where sqrt() gives a lower value than intended (e.g. 49.9999 instead of 50.0001), which would give the wrong result when casting to an integer.

      → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For some unknown reasons, my code even with C++ 17 also gave WA on test case 8. Could it be because of some mysterious behavior of floor function over sqrt()?

→ Reply
»
3 months ago, # |
  Vote: I like it -9 Vote: I do not like it

SAME HAPPENED WITH ME! Then I converted my C++ code into python using GPT then it worked!

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Same Here! C++ Code : https://codeforces.net/contest/2020/submission/283708389 Python Code : https://codeforces.net/contest/2020/submission/283713285

I converted my C++ code to python then it worked.

→ Reply
»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

just do binary search lol

→ Reply
»
3 months ago, # |
← Rev. 4   Vote: I like it +24 Vote: I do not like it

Floating point numbers work completely differently in 32 bit and 64 bit. Currently on CF, C++17 is 32 bit and C++20 and C++23 are 64 bit. I've previously written a blog about this quirk here. TLDR: 32 bit uses long double for computations even if you ask it to use doubles (refered to as "excess precision"). But when stored, the double variables are still stored as doubles, making floating point numbers in 32 bit horribly unreliable.

Your submission here is a perfect example of this. For example, with these two lines your submission gets AC in C++17(32 bit) 283814989

double res = sqrt(m);
int a = res;

However, forcing res to be stored by adding some arbitrary floating point computation before the int a = res line causes the submission to WA in C++17(32 bit) 283815050.

double res = sqrt(m);
pow(res, 2);
int a = res;

I highly recommend that you use long double and submit in 64 bit. That is much better than relying on excess precision.

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The same thing happened with me. I had to code a binary search square root function as well. I will never be using the sqrt function again.

→ Reply