There are better strategies for returning random numbers in a range, in terms of the fraction of values that will be rejected.
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:
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(?).
Yeah this code definitely wasn't designed to win any performance contests. I was mostly optimizing for readability. The easier it is to understand code, the easier it is to audit it from a security perspective.
The author of that blog post admits he doesn't fully understand Lemire's algorithm despite attempting a Rust port of it, and his functions only support a max range of 256 numbers (8 bits), whereas Lemire's version topped out at 64 bits, and the simplistic version I've outlined in this post supports 32 bits.
This isn't a criticism of the post's author of course, because Lemire's algorithm is inherently complex.
2 comments
[ 3.6 ms ] story [ 14.1 ms ] threadThe 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(?).
The author of that blog post admits he doesn't fully understand Lemire's algorithm despite attempting a Rust port of it, and his functions only support a max range of 256 numbers (8 bits), whereas Lemire's version topped out at 64 bits, and the simplistic version I've outlined in this post supports 32 bits.
This isn't a criticism of the post's author of course, because Lemire's algorithm is inherently complex.