writeups

(2016) The comments on this fast range reduction are interesting, I recommend reading them (they're much longer than the post itself). Some highlights: Versions of this exist as early as 1997, in CMU's Common Lisp implementation. Their GitLab is not loading quicky on my computer, but the commit is supposed to be from December by Douglas Crosher (https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-...). The "Further reading" section (and comments) include implementations of the trick in the wild. Stockfish, the chess engine, used this optimization to reduce memory for storing precomputations of moves in their transposition tables (https://github.com/official-stockfish/Stockfish/commit/2198c...). The commit switches from using bitwise AND (&) and power-of-2 table sizes to using the modulo hash trick, which allows for full use of RAM

You may be interested in this work going in the opposite direction, holding the bias constant and extracting the most ranges from a constant amount of randomness: https://github.com/sipa/writeups/tree/main/uniform-range-ext... This work is interesting because generating random bits via strong generators is typically much more expensive than extraction-- so it can be very useful in cases where a number of small random values are needed in a tight loop such as for some kinds of hash table and generating permutations.

I recently discovered a generalization of this approach, which allows mapping a single hash to multiple independent numbers, each in their own range, while maintaining various uniformity properties. A write-up is here, in case anyone is interested: https://github.com/sipa/writeups/tree/main/uniform-range-ext...