4 ms·
If all you need is to uniformly reduce a number into a given range, there is a division-free approach: lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modu
by eutectic 6y ago
If all you need is to uniformly reduce a number into a given range, there is a division-free approach:
lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/%3famp
- eloff 6y agoGo uses this technique internally for generating random numbers in a range. I don't remember if it's used in the map implementation or not, just that I found this code and the link to Daniel Lemire's blog post.
- rurban 6y agoAnd for hash tables with a 128bit hashfunc he doesn't need division nor modulo at all. Only with primed sizes, but with these large sizes primed does not make sense, you always take power of 2 sizes. Then you get the bucket index with a trivial rshift or AND bitmask. So a lot of work for nothing. At least LLVM did profit.
- repiret 6y agoIt took my fat fingers a while to be able to successfully copy-n-paste the link on mobile. Here’s a proper link to save others the hassle: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-...