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.
Thanks for reading!
UPD: Changed divfloor and divceil according to bicsi 's idea.
UPD: nth-root has now been updated to handle entire integer range.
niceee
thanks
To handle overflows you can perform the following check to multiply two integers:
It is nice to encapsulate this into a function (if you want to use it more than once) alike
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 caseb == 0
requires additional care...Thanks a lot... I'll include this in the blog
Just wanted to ask, is the equality really necessary?
This is because if we want to perform
mult(1,9e18)
, whereINF
isLLONG_MAX
, it will not return9e18
, butLLONG_MAX
.Yes, sometimes it returns
INF
instead of a value, that is just slightly less thanINF
, 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 than1e18
, 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$$$.
Cool thanks
__int128_t
For divfloor, I usually just do
a/b - (a%b<0)
and for divceila/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.Added :)
Doesn't the code for floor(logb(x)) cause an infinite loop?
Thanks for pointing out... Fixed