The DiscreteUniformSampler delegates the creation of an integer in the range [0, n) to the UniformRandomProvider.
This sampler will be repeatedly used to sample the same range. The default method in BaseProvider uses a dynamic algorithm that handles n differently when a power of 2.
When the range is a power of 2 the method can use a series of bits from a random integer to generate a uniform integer in the range. This is fast.
When the range is not a power of 2 the algorithm must reject samples when the sample would result in an over-representation of a particular value in the uniform range. This is necessary as n does not exactly fit into the number of possible values [0, 2^31) that can be produced by the generator (when using 31-bit signed integers). The rejection method uses integer arithmetic to determine the number of samples that fit into the range: samples = 2^31 / n. Extra samples that lead to over-representation are rejected: extra = 2^31 % n.
Since n will not change a pre-computation step is possible to select the best algorithm.
n is a power of 2:
n is not a power of 2:
The second method uses a range of 2^32 instead of 2^31 so reducing the rejection probability and avoids the modulus operator; these both increase speed.
Note algorithm 1 returns sample values in a repeat cycle from all values in the range [0, 2^31) due to the use of modulus, e.g.
Algorithm 2 returns sample values in a linear order, e.g.
The suggested change is to implement smart pre-computation in the DiscreteUniformSampler based on the range and use the algorithms that favour the most significant bits from the generator.