Modulo operation in C#, C and OCaml

Question

I wanted to confirm that the modulo operation was an expensive operation so I tested this piece of code that checks if a given number is even: ``` bool is_even(int n) { return (n & 1) == 0; } ``` then this one: ``` bool is_even_bis(int n) { return (n % 2) == 0; } ``` I used C# at first and indeed, the code using logical `&` is faster than the other one, sometimes even three times faster. Using ILSpy I saw that there was no optimization done when compiled to MSIL, the code is strictly the same. However as spotted by a friend of mine in C, using `gcc -O3` the code is compiled to: ``` is_even: mov eax, DWORD PTR [esp+4] # tmp63, n and eax, 1 # tmp63, xor eax, 1 # tmp63, ret ``` and: ``` is_even_bis: mov eax, DWORD PTR [esp+4] # tmp63, n and eax, 1 # tmp63, xor eax, 1 # tmp63, ret ``` So basically strictly the same thing. Even when using `-O0` optimization the operation doesn't even appear: ``` is_even: push ebp # mov ebp, esp #, mov eax, DWORD PTR [ebp+8] # tmp63, n and eax, 1 # D.1837,…

Accepted Answer

Firstly, there is no concept of speed for these operations, in a portable sense. Your assertions might be true for your system, but they're invalid for all systems. For this reason, it's quite pointless speculating on micro-optimisations. You can find far more significant optimisations by producing a program that solves a meaningful problem, profiling it to find the parts of the code that take up the most execution time and introducing faster algorithms for those times. By faster algorithms, I mean better data structures (or less operations), as opposed to different operators. Stop focusing on micro-optimisations!

Your C version of `is_even` isn't well-defined. It might produce negative zeros or trap representations, particularly for negative numbers. Using a trap representation is undefined behaviour.

It seems as though the difference you might be seeing could be caused by signed integer representation on your system. Consider if -1 were to be represented using ones complement `11111111...11111110`. You'd expect `-1 % 2` to result in -1, not 0, wouldn't you? (edit: ... but what would you expect `-1 & 1` to result in, if -1 is represented as `11111111...11111110`?) There needs to be some overhead, to handle this for implementations that use ones complement as signed integer representation.

Perhaps your C compiler has noticed that the `%` expression you used and the `&` expression you used are equivalent on your system, and as a result made that optimisation, but the optimisation hasn't been performed by the C# or OCaml compilers for whatever reason.

Bonus question : I guess the modulo is based on division and since the division is done in O(n²) time (n being the number of digits) can we say that the modulo has quadratic time complexity?

There is no point contemplating the time complexity of these two basic operations, because they'll differ from system to system. I covered that in my first paragraph.

Modulo operation in C#, C and OCaml

Solution

Problem