// the find
lemire/fastrange
A fast alternative to the modulo reduction
A single-header C/C++ library that replaces modulo reduction (`x % p`) with a multiply-shift operation (`(x * p) >> bits`), which avoids integer division. Aimed at hashing, hash table probing, and probabilistic algorithms where you need to map a random word into a bounded range. Backed by a published ACM paper and real-world adoption in TensorFlow.
The core trick is genuinely useful and well-founded — multiply-shift is faster than division on every modern CPU, and the bias argument is rigorous. Single-header, zero dependencies, C and C++ compatible, drops into any project in seconds. The unbiased variant (Lemire's debiasing algorithm) handles the tricky case where you need true uniformity, not just approximate uniformity. Paper-backed with benchmarks and real production validation.
Last touched in 2021 and before that basically 2018 — this is finished, not maintained, which is fine for what it is, but there are no SIMD variants for bulk range-mapping workloads where you might want to vectorize the multiply-shift across a batch. The pre-condition that inputs must span the full word range is easy to violate silently (the `rand()` example warning is good, but there's no assertion or compile-time check). The 32-bit path uses a 64-bit multiply internally, which is fine on x86-64 but worth knowing on 32-bit or embedded targets.