Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

codemode's blog

By codemode, history, 8 months ago, In English,

Say, I have an O(n^2) or O(n^3) solution to a problem . If I use the modulo operator in most of the statements inside the loops, will my program slow down ? With which factor will it slow down ? like 2*x,3*x,.. ? (if "x" is the execution time of the program when no modulo is used)

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

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

It will be a few times slower. Just implement anything and check yourself.

»
8 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

The modulo operation does not affect the time complexity at all. It's a constant time operation just like other basic arithmetic operators. However, the time complexity isn't equal to the actual runtime, which will depend on many factors such as how good your implementation is.

The modulo operation may be slower than other basic operations, but if you blindly replace them with branches such as if statements you might actually slow your program down since an unpredictable branch can be slower than a modulo operation in my experience. In the end, there's no single number that will always predict how much modulo operations slow down your program. It all depends on many factors such as your implementation and your compiler. The only way to know for sure is to try it out and measure the execution time.

For more on branch prediction, see https://stackoverflow.com/a/11227902/9254539

I wanted to write some code to show you modulo vs predictable branch vs unpredictable branch, but I can't reliably prevent the compiler from obliterating my benchmark by optimizing the whole thing out.