Menu
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?
885
The modulus operator is added in the arithmetic operators in C, and it works between two available operands. It divides the given numerator by the denominator to find a result. In simpler words, it produces a remainder for the integer division. Thus, the remainder is also always an integer number only.
A modulo-operation is very slow. An if is most likely to be faster than a modulo and more readable.
Division and modulus are more than twice as expensive as multiplication (a weight 10). The division by two or a multiple of two is always a trick, but not much more can be done without having side-effects. If you can replace division by multiplication, you do get a speed-up of more than two.
So in simple terms, this should give you a feel for why division and hence modulo is slower: computers still have to do long division in the same stepwise fashion tha you did in grade school.
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 == 22 - 16 == 6 Dec Bin ----- ----- 22 = 10110 8 = 01000 8 - 1 = 00111 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.
65
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
