roycf123's blog

Dealing with integers, evading precision errors in C++
By roycf123, 7 months ago, In English

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.

  • Vote: I like it
  • +60
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

niceee

→ Reply
»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

thanks

→ Reply
»
7 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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...

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot... I'll include this in the blog

    → Reply
  • »
    »
    6 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      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$$$.

      → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

__int128_t

→ Reply
»
7 months ago, # |
  Vote: I like it +27 Vote: I do not like it

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.

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Doesn't the code for floor(logb(x)) cause an infinite loop?

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks so much

→ Reply