3 ms·
> In particular, it is free to modularly reduce by this prime (take the bottom 43112609 bits) Am I missing something? 2^3 - 1 is a Mersenne prime; but taking
by mlyle 6y ago
> In particular, it is free to modularly reduce by this prime (take the bottom 43112609 bits)
Am I missing something? 2^3 - 1 is a Mersenne prime; but taking a number mod 7 is not taking the 3 low bits (there's a relatively low cost trick to take numbers modulo b-1, the same "divide by 9" tricks we can do in base 10... but it's not as easy as looking at the last digit).
- deleted 6y ago[deleted]
- linknoid 6y agoThe simple trick with modulo 7 is take all the 3 bit sequences: (x & 111), (x & 111000) >> 3, (x & 111000000) >> 6, etc. and add them all together. It means you just have to do bitshift + add instead of all the complexity of division. Same applies to higher powers of 2^n-1 as well.
- SamReidHughes 6y agoYou can also combine those shift/adds by multiplying by a 1001001001 pattern or perhaps some 1000001000001 patterns.
- mlyle 6y agoSure. That's why I said it was the same as the mod 9 tricks in base 10.
- blintz 6y agoYeah, sorry, there are extra steps here. If n= 43112609 and you have some 2n-bit number to reduce, you can split it into two n-bit words and simply add the words together, since 1 = 2^n (mod 2^n - 1). You can do this very quickly (ie you can add an arbitrary number of 2n -bit values together with only a small number of adds and shifts as overhead).
- mlyle 6y agoYah-- as mentioned-- just like we can find the residue mod 9 by adding digits up in base 10. There's notably also the all 1's case to deal with as an exception.