Hacker News Reader

> 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).

View on HN

The 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.

You can also combine those shift/adds by multiplying by a 1001001001 pattern or perhaps some 1000001000001 patterns.

Sure. That's why I said it was the same as the mod 9 tricks in base 10.

Yeah, 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).

Yah-- 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.

Reply on news.ycombinator.com