FastMod

Compute a % b about 5 times faster than usual, where b is constant but not known at compile time. Returns a value congruent to a pmod b in the range [0, 2b).

8 lines proven correct, stress-tested Measured as having 4 times lower latency, and 8 times higher throughput, see stress-test.

content/various/FastMod.h — Simon Lindholm, source: https://en.wikipedia.org/wiki/Barrett_reduction

typedef unsigned long long ull;
struct FastMod {
	ull b, m;
	FastMod(ull b) : b(b), m(-1ULL / b) {}
	ull reduce(ull a) { // a % b + (0 or b)
		return a - (ull)((__uint128_t(m) * a) >> 64) * b;
	}
};