by ksbrooksjr on 11/21/23, 12:55 AM with 2 comments
by jepler on 11/21/23, 1:24 AM
The code shown here recognizes the problem (the example of generating numbers from 0 to 25 inclusive) and finds a construct that makes things better (the modulo some-power-of-two step), but it's possible to do better and have nearly no rejections.
Here's a really good tutorial on some further steps that can be taken to reduce the quantity of numbers sampled, and make it faster to reject unusable numbers:
https://sts10.github.io/2020/10/10/lemire-neaarly-divisionle...
However, the initial / best example assumes that 128 bit arithmetic types are available and reasonably efficient and I think that may not even be true in typescript(?).