Minor Description
Improve the performance of array shuffling by generation of multiple indices in a range [0, n) from a single sample from a random source.
The current UniformRandomProvider method to sample an integer in a range [0, n) uses a rejection method based on multiplication with a single use of a slow modulus operator if rejection is required. The author of that method has extended it to allow generation of multiple integers from 2 or more ranges from the same random sample.
When applied to a shuffle algorithm the speed-up can be significant, typically in the range of up to 2-fold for smaller arrays depending on the speed of the random generator; slower generators see a greater speed-up.
The method is described in:
Nevin Brackett-Rozinsky, Daniel Lemire, Batched Ranged Random Integer Generation, Software: Practice and Experience (to appear)
See arXiv:2408.06213M.
See also Daniel Lemire Blog: Faster random integer generation with batching
