Most optimized way to calculate modulus in C

Question

I have minimize cost of calculating modulus in C. say I have a number x and n is the number which will divide x

when n == 65536 (which happens to be 2^16):

mod = x % n (11 assembly instructions as produced by GCC) or
mod = x & 0xffff which is equal to mod = x & 65535 (4 assembly instructions)

so, GCC doesn't optimize it to this extent.

In my case n is not x^(int) but is largest prime less than 2^16 which is 65521

as I showed for n == 2^16, bit-wise operations can optimize the computation. What bit-wise operations can I preform when n == 65521 to calculate modulus.

Answer 1

First, make sure you're looking at optimized code before drawing conclusion about what GCC is producing (and make sure this particular expression really needs to be optimized). Finally - don't count instructions to draw your conclusions; it may be that an 11 instruction sequence might be expected to perform better than a shorter sequence that includes a div instruction.

Also, you can't conclude that because x mod 65536 can be calculated with a simple bit mask that any mod operation can be implemented that way. Consider how easy dividing by 10 in decimal is as opposed to dividing by an arbitrary number.

With all that out of the way, you may be able to use some of the 'magic number' techniques from Henry Warren's Hacker's Delight book:

• Archive of http://www.hackersdelight.org/
• Archive of http://www.hackersdelight.org/magic.htm

There was an added chapter on the website that contained "two methods of computing the remainder of division without computing the quotient!", which you may find of some use. The 1st technique applies only to a limited set of divisors, so it won't work for your particular instance. I haven't actually read the online chapter, so I don't know exactly how applicable the other technique might be for you.