### Raito_Yagami's blog

By Raito_Yagami, history, 2 months ago,

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

• -10

 » 2 months ago, # |   +30 I used sqrtl and AC B in my first try
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   +11 yeah binary search implementation is great but usually sqrtl works. Sad for you u solved only A :((
•  » » » » 2 months ago, # ^ |   +3 It's ok, I'm used to heavy drops
•  » » » » 2 months ago, # ^ |   +24 Sad for you u use alt to reply :((
•  » » » » » 2 months ago, # ^ |   -20 Sad for you u are expected to have -51 rating change as expected by carrot :((
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   +31 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 :((
•  » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   -14 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.
•  » » » » » » » » 2 months ago, # ^ |   +16 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
•  » » » » » » » » » 2 months ago, # ^ | ← Rev. 4 →   -14 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, hereAnd 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 blogHowever, PEACE out! I see this discussion of no relation to the post Good luck for your CP journey.
•  » » » » » » » » 2 months ago, # ^ |   +4 What proves to you I use alt accounts in contests? Well, technically you are newbie.
•  » » » 2 months ago, # ^ |   +6 sqrtl works fine for numbers up to $2^{62}$, which is imo enough for most cases. source
•  » » » » 2 months ago, # ^ |   0 Good piece of information. Thanks ✪ω✪
 » 2 months ago, # |   0 Educational round proving itself why it is educational
 » 2 months ago, # |   +6 I just used plain old sqrt (with long double) and brute forced the correct value assuming that the precision error is at most +/-10
 » 2 months ago, # |   0 I used sqrtl then I got accepted B
 » 2 months ago, # |   +9 Spoilerll x=sqrtl(n); while(x*xn)x--; // now x is the precise sqrt 
•  » » 2 months ago, # ^ |   0 I write binary search this way (after log part), when I am lazy to think)
 » 2 months ago, # |   -8 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaah im so angry and happy i learnt something. I used sqrt() and not sqrtl() but still AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
 » 2 months ago, # | ← Rev. 2 →   0 This gave me AC with sqrt Codell n; cin >> n; ll ans = sqrt(n); if(ans * ans != n) ans++; cout << ans -1 << "\n"; Upd: Maybe I Just made 2 mistakes that are Canceling each other
•  » » 2 months ago, # ^ |   -19 You might get hacked/fst
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 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 Testtest: 5 971498963823460897 971498963823460899 971498963823460900 971498963823460901 971498963823460905 Local : 985646470 985646470 985646469 985646470 985646470 Codeforces: 985646469 985646469 985646469 985646470 985646470 
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 you are wrongstd::sqrt precision is good enough to work on integers (at least up to long long)(edit: in c++ 17)
 » 2 months ago, # | ← Rev. 2 →   +10 Can anyone give an actual example where you should use binary search instead of std::sqrt? Never had any precision problems for integers with sqrtEdit: 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
•  » » 2 months ago, # ^ |   0 C++ is evolving backwards
•  » » 2 months ago, # ^ |   0 i actually had precision issues with c++17 in a previous contest, (this is my alt's submission because that day i could only give first hour of contest) https://codeforces.com/contest/1737/submission/174985763you can verify if you replace sqrt with sqrtl this is correct
•  » » » 2 months ago, # ^ |   0 Then what I said was right
 » 2 months ago, # |   0 sad story
 » 2 months ago, # |   0 //MATH G(n); if(n==1) { print(0); return; } if(n==2 or n==3) { print(1); return; } cout<<(ll)sqrt(n-1)<>1; ll ert=mid*mid; if(ert>=n) { r=mid-1; } else { l=mid+1; } // debug(ert); } print(r);
 » 2 months ago, # |   0 Auto comment: topic has been updated by Raito_Yagami (previous revision, new revision, compare).