Fast modulo

[kth-competitive-programming]

Fast modulo

[simonlindholm]

https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/

[simonlindholm]

Barrett reduction seems to work out well, assuming a 64-bit system: https://gist.github.com/simonlindholm/0aa4c140e58a584264f929b338ef870a

About as fast as GCC's codegen and as Montgomery multiplication. Montgomery multiplication only uses 32-bit instructions, which is helpful on CF, but is more code and harder to use.

In concrete terms, the throughput is about 8x better than a dynamic modulo instruction, and latency about 3x better.

The lemire link should be even faster (esp. for divisibility tests), but sadly only works for 32-bit numerators (on a 64-bit system).

[simonlindholm]

So short that I might as well include it. It's easy enough to throw out again if we need space.