3 ms·
Also as mentioned elsewhere in the comments, modulo is expensive, even more for non-powers of 2
by RBerenguel 10y ago
Also as mentioned elsewhere in the comments, modulo is expensive, even more for non-powers of 2
- pklausler 10y agoModulus by a power of two is cheap. Modulus by a constant is a multiplication by reciprocal and a shift. And if your argument is in [0..2N], mod N is just a conditional subtraction that doesn't even require a branch.
- CorvusCrypto 10y agocheap is relative right? I mean a multiplication can be spread over shift and add/sub instructions whereas a mask is just one instruction I think right?
- tbirdz 10y agoThat's only true if your compiler actually outputs a modulus instruction when it sees you doing N % pow2. It really should optimize that into N & (pow2-1) for you, so whether you write the & or the % it will end up running the cheap & version.