Raito_Yagami's blog

Just a reminder
By Raito_Yagami, history, 2 months ago, In English

Don't use sqrt because precision issues

Also here is implementation to find floor(sqrt(x))

#define int long long
int sqrt(int x){
    int l=1,r=1e9+5,ans=0,mid;
    while (l<=r){
        mid=(l+r)/2;
        if (mid*mid<=x){
            ans=mid;
            l=mid+1;
        }else r=mid-1;
    }return ans;
}

It seems std::sqrt works fine in C++17 though. Also sqrtl seems to give correct results

  • Vote: I like it
  • -10
  • Vote: I do not like it

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

I used sqrtl and AC B in my first try

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

    I'm not sure about sqrtl, but I think it might have precision issues too. I think coding sqrt using binary search can be best because it's dealing with integers.

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

      yeah binary search implementation is great

      but usually sqrtl works. Sad for you u solved only A :((

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

        It's ok, I'm used to heavy drops

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

        Sad for you u use alt to reply :((

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

          Sad for you u are expected to have -51 rating change as expected by carrot :((

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

            I used sqrtl and AC B in my first try

            Sad for you, your blogs talks about people breaking the contest rules, yet u break them and admitting it :((

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

              Hmm. I guess your logic has some holes. What proves to you I use alt accounts in contests? Maybe, I used sqrtl and submitted on my main account during contest time and I just use this alt account for sharing some useful piece of info as I don't like writing from my main.

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

                I just use this alt account for sharing some useful piece of info as I don't like writing from my main.

                Could you provide an example ?

                Based on what I've seen in your blogs, it appears to me that you engage in contribution farming

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

                  More holes in your logic. Wasn't sharing the helpfulness of sqrtl() in such problems for c++20 something useful? that it got +29 ups. Another past incidence, a colleague of yours Yousef_Sameh asked for help regarding map and unordered_map and I explained why the HashMap got TLE thru hacks, here
                  And isn't this your comment and this also . It looks to me you engage in contribution farming.

                  Aren't those mentioned comments contribution farming? Besides most of my contribution was got from catching cheaters who spoil the platform or thanking Mike for his efforts like this blog

                  However, PEACE out! I see this discussion of no relation to the post

                  Good luck for your CP journey.

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

                What proves to you I use alt accounts in contests?

                Well, technically you are newbie.

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

      sqrtl works fine for numbers up to $$$2^{62}$$$, which is imo enough for most cases. source

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

Educational round proving itself why it is educational

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

I just used plain old sqrt (with long double) and brute forced the correct value assuming that the precision error is at most +/-10

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

I used sqrtl then I got accepted B

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

    I write binary search this way (after log part), when I am lazy to think)

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

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaah im so angry and happy i learnt something. I used sqrt() and not sqrtl() but still AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

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

This gave me AC with sqrt

Code

Upd: Maybe I Just made 2 mistakes that are Canceling each other

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

    You might get hacked/fst

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

      I tried to hack me now, In Local i got WA but in codeforces i got AC(Unsuccesfull hacking attempt) I think i'm lucky today. I switched to GNU C++20 (64) and got WA too

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

      you are wrong

      std::sqrt precision is good enough to work on integers (at least up to long long)

      (edit: in c++ 17)

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

Can anyone give an actual example where you should use binary search instead of std::sqrt? Never had any precision problems for integers with sqrt

Edit: it seems like there are no problems on c++ 17 but when I switch to c++ 20 it fails. Either way, writing binary search for sqrt seems too boring, just use c++ 17

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

sad story

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

G(n);
if(n==1)
{
    print(0);
    return;
}
if(n==2 or n==3)
{
    print(1);
    return;
}
cout<<(ll)sqrt(n-1)<<nl;




//binary search
G(n);
ll l=0,r=INF;
while(l<=r)
{
    ll mid=l+r>>1;
    ll ert=mid*mid;

    if(ert>=n)
    {
        r=mid-1;
    }
    else
    {
        l=mid+1;
    }
    // debug(ert);
}
print(r);
→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply