Is modulo still slow when first number is smaller?

general
1

(To the mods: There was a similar thread accidentally posted by me before I could type out the complete query. It was the space bar which triggered the ‘Create Topic’ button and I have no idea why would that happen. :woman_shrugging: I’ve deleted the earlier thread)

Hello community!

Lets say I’m solving a question which needs the answer modulo some number M. (a common scenario in competitive programming questions)

To give an easy example, assume that my solution code is something like this. (Yes the code does not do anything. I just need to put up a simple example.)

#include <bits/stdc++.h>
using namespace std;

int M = 10007;

int main() {
  int n, ans;
  cin >> n;

  for (int i = 0; i < n; ++i) {
    ans += i * 100;
    ans %= M; // I do modulo here
  }

  cout << ans;
  return 0;
}

I have read that the modulo operation is slow, which will eventually affect my program runtime if I do modulo oeration at every iteration of the loop.

To try get around this and possibly optimize this, I replace

ans %= M;

with

if (ans >= M)
  ans  %= M;

Now, I’m doing a comparison at every iteration of the loop, but I’m not doing modulo every time. Does this make my code more efficient?

My intention was to reduce the number of times modulo operation is called so that the runtime is reduced. However, to achieve that, I’ve introduced a comparison in every iteration. Will that backfire?

To be more clear, I’m talking about C++. Does the compiler automatically optimize my code in the manner I’ve said, even if I don’t include the comparison part? (and thus making my last code snippet redundant)

In simple words, is the modulo operation still slow even when the first number is smaller than the second number?

Thanks! :smiley:

2

I think when you do modulo at every loop, it should be faster than when you do the modulo when it’s greater than M, because modulus of an integer greater than M will take more time than modulus of an integer which is always less than M in every loop. I may not be sure of this one…

3

Modulo follows Euclidean Division process. I think you have your answer now.

1 Like
4

If I understand the process correctly, this means that a\%M isn’t a slow process when a<M. Since the algorithm moves forward only when a \geq M, it would exit right in the first step if a<M.

Am I interpreting it right?

1 Like