codemode's blog

By codemode, history, 22 months ago,

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)

• +4

 » 22 months ago, # |   +17 It will be a few times slower. Just implement anything and check yourself.
•  » » 10 months ago, # ^ |   0 I was doing Longest Divisible Subset Problem. In that I did it by two approaches. (1) Sorted the array and then applied a%b once (2) Didnt sort the array and applied a%b and b%a to check twice.I got higher execution time in 2nd scenario, though I expected it should be in 1st as I am sorting the array that takes O(nlogn) while modulo operators take O(1) I suppose.Why did this happen?Please reply and help me out Mr. Legend!Would be so happy if you reply as I am your huge fan!Love from India!
•  » » » 10 months ago, # ^ |   +14 Modulo operations are slow, that's the reason. Running time and complexity aren't the same thing.
 » 22 months ago, # | ← Rev. 2 →   +3 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/9254539I 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.
 » 6 weeks ago, # |   -12 you can feel of it when you see my submission in 1st every thing is same except I used modulo for every iteration which gives me straight TLEand then when I don't apply in each iteration it takes 62 msbad code 111795934good code 111799139