Dark_Knight_3's blog

Doubt regarding sqrt function in G++ 17 and 23
By Dark_Knight_3, history, 2 months ago, In English

In the recent Codeforces Round 976 (Div. 2) and Divide By Zero 9.0 contest, I submitted my solution for 2020B - Да будет свет! in C++ 23. There, I got the wrong answer on G++ 23, but after the contest, I solved it by changing the language to G++ 17, and it got accepted. So what was the problem? Should I be using G++ 17 or G++ 23? What should be considered when using the built-in sqrt() function? Like precision, etc.. G++ 17 solution 283662762 G++ 23 solution 283597439

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Dark_Knight_3 (previous revision, new revision, compare).

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

Auto comment: topic has been updated by Dark_Knight_3 (previous revision, new revision, compare).

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

You should be using either sqrtl or binary search.

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

    But the same code that got WA on 8 with G++ 23 got accepted with G++ 17. In that code, sqrt() worked. I was having this confusion.

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

sqrt() uses floating point, so its not "reliable". Use floating point in CP as less as you can. Use binary search.

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

Actually when you need precise answer for large inputs always go for sqrtl instead of sqrt because sqrt returns a floating interger where as sqrtl returns value in double which has more accuracy than float so using sqrtl is always a better choice irrespective of compiler(But compilers do make significant difference in TC)..Hope this helps

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I made a blog about why not to use C++ 17 Here

If some problems work only in C++ 20 / C++ 23 and some other Problems work only in C++ 17, we need a fix for this problem.

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

    Ok, I will read the blog.

    → Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    I doubt that you've calculated the complexity of that solution. I can force your solution to do about sqrt(N) operations per test case, multiply that by the number of cases and it's not as small as you think.

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

      Bro, the 2 solutions are the exactly same except for one being C++ 17 and the other one being C++ 20.

      Let's say that I didn't calculate the time complexity.

      But still, the other one is accepted.

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

        Let's quote the blog: "I calculated the time complexity and it is way smaller than the time limit."

        No you didn't.

        Some differences of runtime are to be expected. There's some weird behavior of some C++ version that happens when you read something using cin and do some operations inbetween, I'm not sure exactly how.

        Still for most problems that you'll find out there if you have a good solution that won't matter.

        → Reply
    • »
      »
      »
      2 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Are you discussing this solution .

      void solve()
{
    ll k;
    cin >> k;
    ll n = sqrtl(k);
    n += k;
    ll c = sqrtl(k);
    // cout << n -(int)sqrt(n)<< " ";
 
    while (true)
    {
        if (n - (ll)sqrtl(n) != k)
        {
            n++;
            c++;
        }
        else
        {
            break;
        }
        // n++;
        // c++;
    }
    cout << c + k << "\n";
}

      Maybe the complexity is taken down by adding sqrt(k) in the first time of answer as it is necessary to be added, and then n++ would work as there would be a lot of difference between the next two consecutive perfect square numbers when we go for large values.

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

I usually write a custom function to fix this and it works all the time ¯_(ツ)_/¯

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

    The custom function that you use is using binary search or something else.

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

      nah, I still use sqrt(x) but I've solved the precision error by integer multiplication.

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

        Ok, I understood it by reading one of your solutions. It is a good method. Thankyou(ෆ˙ᵕ˙ෆ)♡.I will also use this.

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

https://mirror.codeforces.com/contest/2020/submission/283800077 this is wa

https://mirror.codeforces.com/contest/2020/submission/283666517 this is ac

i dont know why

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    https://mirror.codeforces.com/blog/entry/134539 In this blog, they had talked about this if I remove these three lines from your code, it is AC // #pragma GCC optimize("Ofast") // #pragma GCC optimize ("unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") But I don't know the reason.

    → Reply