Abito's blog

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

Comments Comments (32)
| Write comment?
»
20 months ago, # |
  Vote: I like it +30 Vote: I do not like it

I used sqrtl and AC B in my first try

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

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

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

        Sad for you u use alt to reply :((

        → Reply
        • »
          »
          »
          »
          »
          20 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
          • »
            »
            »
            »
            »
            »
            20 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
            • »
              »
              »
              »
              »
              »
              »
              20 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
              • »
                »
                »
                »
                »
                »
                »
                »
                20 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
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  20 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
              • »
                »
                »
                »
                »
                »
                »
                »
                20 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
            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
              ← 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
              • »
                »
                »
                »
                »
                »
                »
                »
                9 months ago, # ^ |
                  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
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 months ago, # ^ |
                  ← 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
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 months ago, # ^ |
                    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
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 months ago, # ^ |
                  ← Rev. 4   Vote: I like it -19 Vote: I do not like it

                  I shouldn't tell info about my life here bro, but I have ✪ω✪

                  I would advise you to stop farming contribution Abdelaleem. Hey!! One more _Sage. Active 17 min ago. This is ur alt it was named Abdelaleem-OR-Yousef ✪ω✪ Let me add it in the blog. For the reader, to verify, https://codeforces.me/profile/Abdelaleem-OR-Yousef

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

    You might get hacked/fst

    → Reply
    • »
      »
      »
      20 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
    • »
      »
      »
      20 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
»
20 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
»
20 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
»
20 months ago, # |
  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
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I upsolved some questions today and done this, i feltit magic, changing compiler ot 20, it get to wrong answer Like there undefined behavior with those built ins. Did a google dork for codeforce about sqrt with binary search as i remember encountering on leetcode, and found this great way. Thank

→ Reply