Блог пользователя Mooncrater

Fastest way to implement Modulo
Автор Mooncrater, история, 4 года назад, По-английски

See these two submissions:

A

B

The only difference between the two being that A uses a hand-made function I stole from here:

int add(int a, int b) {
 	int res = a + b;
 
 	while (res >= MOD) res -= MOD;
 
 	while (res < 0) res += MOD;
 
 	return res;
}

This function is easy to understand. I am just not sure, why using this only, the running time of the program went down from 936ms to 561ms. That difference is bigger than expected. Can anyone help with, why is this happening? Why exactly is this function faster than simply using %MOD?

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Modulo is an expensive operator. When you use your custom made function to add, it only uses the modulo operator when it is needed. When the value of res is between 0 and MOD-1, we don't need to mod it and we can save time.

→ Ответить
»
4 года назад, # |
← Rev. 4   Проголосовать: нравится +12 Проголосовать: не нравится

Your hand-made function is faster because you are taking the modulo of a small number (it is the sum of 2 number smaller than MOD), so you are adding/substracting MOD at most one time. If instead the addition you do a moltiplication betweet the two numbers the result will become really big and your hand made function will become very very slower than the % operator because in worst case you function do MOD operations.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

I think that : int res = a + b; is wrong since the addition of 2 ints can overflow, and therefore should be :

int res = a % MOD + b % MOD;

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +19 Проголосовать: не нравится

    If both a and b are in range [0,MOD-1] and MOD is less than INT_MAX/2, which is usually the case, then it's correct.

    The whole point of this is to avoid using the modulo operator and it is commonly used when dealing with modulos. Also the original code can be shortened if the constraints i stated above hold.

    int add(int a,int b){
    a+=b;
    if(a>=MOD)
        a-=MOD;
    return a;
}

    This code will do the trick just fine. And if you want to do subtraction you can use this:

    int sub(int a,int b){
    a-=b;
    if(a<0)
        a+=MOD;
    return a;
}
    → Ответить