Search code examples
c#mathoptimizationmodulus

Faster modulus in C/C#?

Is there a trick for creating a faster integer modulus than the standard % operator for particular bases?

For my program, I'd be looking for around 1000-4000 (e.g. n%2048). Is there a quicker way to perform n modulus 2048 than simply: n%2048?

Solution

  • If the denominator is known at compile time to be a power of 2, like your example of 2048, you could subtract 1 and do a bitwise-and.

    That is:

    n % m == n & (m - 1)

    ...where m is a power of 2.

    For example:

    22 % 8 == 6

         Dec       Bin
       -----     -----
22 & (8 - 1) =   10110 
               & 00111 
               -------
           6 =   00110

    Bear in mind that a good compiler will have its own optimizations for %, maybe even enough to be as fast as the above technique. Arithmetic operators tend to be pretty heavily optimized.