3 ms·
"An intuitive way to think about "fast range" technique is scaling. Number x ranges [0,2^32−1], multiplying it by N then divide by 2^32, the range becomes [0,N−
by bra-ket 7y ago
"An intuitive way to think about "fast range" technique is scaling. Number x ranges [0,2^32−1], multiplying it by N then divide by 2^32, the range becomes [0,N−1].
From "Writing a Damn Fast Hash Table With Tiny Memory Footprints": http://www.idryman.org/blog/2017/05/03/writing-a-damn-fast-hash-table-with-tiny-memory-footprints/ http://www.idryman.org/blog/2017/05/03/writing-a-damn-fast-h... , previous discussion https://news.ycombinator.com/item?id=14290055 https://news.ycombinator.com/item?id=14290055
- nullc 7y agoThis approach comes naturally to people working with fixed-point math: Your random value is a UQ32 fixed-point fractional value, you multiply it by a UQ32.0 size resulting in a UQ32.32 value that you shift back down to UQ0. [ https://en.wikipedia.org/wiki/Q_(number_format) https://en.wikipedia.org/wiki/Q_(number_format) ] I wonder if the introduction of calculators into school curriculum has made people less prone to carry around rational values as intermediates. Division is a pain in the butt in mental arithmetic and it remains slow on computers (except when compilers are able to strength-reduce it away). There are a lot of nice optimizations in numerical algorithms that come from keeping denominators seperate (implicitly or explicitly).
- djmips 7y agoI was thinking the same thing because I'm older I grew up on 8 bits and this sort of thing comes more naturally to me. It's a nice article but does it deserve to be called the 'Lemire technique'. :)