Fastrange: A fast alternative to the modulo reduction

[henrikm85]

https://github.com/lemire/fastrange

[dmitrygr]

This is how we've been doing division by a constant in the embedded world since...forever

this is so well known in fact that arm gcc defaults to this when a proper constant exists if you do division or modulus operator...

[lvs → dmitrygr]

I was going to say, this is an ancient and well-known optimization. I have no idea how old it is, but I would venture it's been a regular practice for at least two decades.

[rkwasny]

Shouldn't a good compiler apply this type of optimisations?

[AstralStorm → rkwasny]

It generally does. (GCC, Clang and ICC) But it cannot simplify the operation on some architectures or when the factor is variable.

The "fastrange" is a very different operation on prime factors than modulo.