Faster remainders when the divisor is a constant: beating compilers & libdivide

While GNU GCC and the Go compiler still rely on the approach developed by Granlund and Montgomery, other compilers like LLVM’s clang use a slightly improved version described by Warren in his book Hacker’s Delight. In some instances, libdivide can even be more efficient than compilers because it uses an approach introduced by Robison (2005) where we not only use multiplications and shifts, but also an addition to avoid arithmetic overflows. In concrete terms, here is the C code to compute the remainder of the division by some fixed divisor :

To test it out, we did many things, but in one particular tests, we used a hashing function that depends on the computation of the remainder.

Source: lemire.me