Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Abito's blog

Just a reminder
By Abito, history, 4 years 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

Comments Comments (28)
| Write comment?
»
4 years ago, hide # |
 
Vote: I like it +30 Vote: I do not like it

I used sqrtl and AC B in my first try

→ Reply
  • »
    »
    4 years ago, hide # ^ |
     
    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
    • »
      »
      »
      4 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        4 years ago, hide # ^ |
         
        Vote: I like it +3 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        4 years ago, hide # ^ |
         
        Vote: I like it +24 Vote: I do not like it

        Sad for you u use alt to reply :((

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, hide # ^ |
           
          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
          • »
            »
            »
            »
            »
            »
            4 years ago, hide # ^ |
            ← 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
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, hide # ^ |
              ← 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
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, hide # ^ |
                 
                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
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, hide # ^ |
                 
                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
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, hide # ^ |
              ← Rev. 5  
              Vote: I like it +18 Vote: I do not like it

              I found the blog on recent actions, and found this ultra funny 😂

              I break contest rules ? Then what about you, pro div2E solver 😂 ? 5

              You can check here.

              Is atcoder_merchant your alt ? (I guess yes by >90%) And I know that Wegz-Saleny is your alt. (bas wegz 7kaya wla eh r2yak, b7bo bsra7a ? Eskndrya gamda fash5 w account da 7kaya brdo mmmkn ytft7 mno mwade3 ktyyr ama nrag3 submission xD)

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, hide # ^ |
                 
                Vote: I like it -27 Vote: I do not like it

                Hello There.

                Yes, I admit that Wegz-Saleny was my alt.

                During the contest, I was taking part with my alt, I switched with my main to take a look at the leaderboard, to take a look at my peers.

                That's when I submitted my main instead of my alt in Problem C, resulting in my solutions getting skipped.

                I have stopped doing this action from that time (participating with alt) and instead participating with my main and not caring about the end result and I regret that action.

                I don't know who is atcoder_merchant.

                Lastly, I would advise you to go practice, touch grass, or do something useful. Paying attention to others is an indicator of insecurity.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, hide # ^ |
                  ← Rev. 5  
                  Vote: I like it -8 Vote: I do not like it

                  You and your alt solved Div2E. So pro 😂. I think I know that alt btw, and it isn't yours xD Btw, the skip had been for E 😉

                  In addition, alting became prohibited per Mike's Single acc policy. You can check the blog that you downvote. It includes lots of examples on those alts smurfing.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, hide # ^ |
                   
                  Vote: I like it +16 Vote: I do not like it

                  Heap_OverFlow

                  Ever consider stepping away from these types of blogs/comments? Maybe it's time to find a life, bro! xD

                  → Reply
    • »
      »
      »
      4 years ago, hide # ^ |
       
      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
»
4 years ago, hide # |
 
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
»
4 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it
Spoiler
→ Reply
»
4 years ago, hide # |
← 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
  • »
    »
    4 years ago, hide # ^ |
     
    Vote: I like it -19 Vote: I do not like it

    You might get hacked/fst

    → Reply
    • »
      »
      »
      4 years ago, hide # ^ |
      ← 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
    • »
      »
      »
      4 years ago, hide # ^ |
      ← 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
»
4 years ago, hide # |
← 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
»
4 years ago, hide # |
 
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
»
4 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply