Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### roycf123's blog

By roycf123, 4 weeks ago,

This is my first time actually trying to contribute something, so please go easy on me....

Hello Codeforces! After a long time of search for a cure for precision errors in C++ while dealing with just integers, I was motivated to write a blog for a curated collection of one. Sure some common ones do already exist in the previous blogs, some really cool ones can be found while browsing other programmers' templates, but why not have a blog which saves the time of search and makes it easier for CP Enthusiasts to improve?

I have implemented a few as follows (may include the common ones):

1) ceil(a/b) and floor(a/b): Handling negative division as well...

ll divceil(ll a,ll b){ return a/b+(a%b>0);}
ll divfloor(ll a,ll b){ return a/b-(a%b<0);}


2) power(a,b):

ll binpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res*=a;
a*=a,b>>=1;
}
return res;
}


3) Floor(logb(x)):

ll lg(ll x,ll b=2){
if(b==1) return -1; //Modify this as per need
if(b==2) return 63-__builtin_clzll(x); //O(1) for log2
ll p=1,ans=0;
while(true){
if(p>x) return ans-1;
if(p>LLONG_MAX/b) return ans;
p*=b,ans++;
}
}


4) nth-root (general): Thanks to LeoPro for the trick to deal with overflows

const ll INF = LLONG_MAX  // You may change ll to ull and LLONG_MAX to ULLONG_MAX

ll mult(ll a,ll b){
if(b==0) return 0;
return a>INF/b?INF:a*b;
}

ll binpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=mult(res,a);
a=mult(a,a),b>>=1;
}
return res;
}

ll bin_nth_rt(ll x,ll n){
if(x==1||n==1) return x;
if(x==INF) x--;    // Doesn't make a difference in answer, and check function fails for INF
ll l=0,r=x,m;
while(r-l>1){
m=l+(r-l)/2;
if(binpow(m,n)>x) r=m;
else l=m;
}
return l;
}


Please feel free to highlight any errors, or areas with room for improvement in performance, handling overflows, divide by zero, etc and contributing your own in the comments.

UPD: Changed divfloor and divceil according to bicsi 's idea.

UPD: nth-root has now been updated to handle entire integer range.

• +60

 » 4 weeks ago, # |   +8 niceee
 » 4 weeks ago, # |   +3 thanks
 » 4 weeks ago, # |   +9 To handle overflows you can perform the following check to multiply two integers: const ll INF = LLONG_MAX; // or 1e18 + 1e9, or anything else you like ll a, b; ... ll c = (a >= INF / b ? INF : a * b); It is nice to encapsulate this into a function (if you want to use it more than once) alike ll mult(ll a, ll b) { return (a >= INF / b ? INF : a * b); } Note that it is allowed to call mult on already overflowed values, the result still is INF. For example, mult(mult(1e15, 1e15), 42) is fine.P. S. This only works for positive integers. For possible negatives you can just replace checks with abs(a) >= INF / abs(b) and case b == 0 requires additional care...
•  » » 4 weeks ago, # ^ |   0 Thanks a lot... I'll include this in the blog
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 Just wanted to ask, is the equality really necessary?This is because if we want to perform mult(1,9e18), where INF is LLONG_MAX, it will not return 9e18, but LLONG_MAX.
•  » » » 11 days ago, # ^ | ← Rev. 2 →   +3 Yes, sometimes it returns INF instead of a value, that is just slightly less than INF, but it is usually unimportant in competitive programming: either you can prove, that there could occur no overflow, or you want to know, whether the number is less than 1e18, or not.In fact, your version is indeed correct, but it wasn't obvious for me, and better safe than sorry. I guess I have somewhere seen a blog about that, but can't find it now, so here's a quick proof, in case anyone wants: Bad case is $ab > INF \iff a > \frac{INF}{b}$ and an integer is greater than a floating point number iff it's greater than its rounding down. Therefore, $a > \frac{INF}{b} \iff a > \lfloor\frac{INF}{b}\rfloor$.
•  » » » » 11 days ago, # ^ |   0 Cool thanks
 » 4 weeks ago, # |   0 __int128_t
 » 4 weeks ago, # |   +27 For divfloor, I usually just do a/b - (a%b<0) and for divceil a/b + (a%b>0). It’s usually the fastest, as most architectures do division and modulo at the same time anyways, and compilers know to optimize this pattern.
•  » » 4 weeks ago, # ^ |   0 Added :)
 » 4 weeks ago, # |   0 Doesn't the code for floor(logb(x)) cause an infinite loop?
•  » » 4 weeks ago, # ^ |   0 Thanks for pointing out... Fixed
 » 4 weeks ago, # |   0 thanks so much