Description
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 overrepresentation 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 31bit 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 overrepresentation are rejected: extra = 2^31 % n.
Since n will not change a precomputation step is possible to select the best algorithm.
n is a power of 2:
// Favouring the least significant bits // Precompute int mask = n  1; return nextInt() & mask; // Or favouring the most significant bits // Precompute int shift = Integer.numberOfLeadingZeros(n) + 1; return nextInt() >>> shift;
n is not a power of 2:
// Sample using modulus // Precompute final int fence = (int)(0x80000000L  0x80000000L % n  1); int bits; do { bits = rng.nextInt() >>> 1; } while (bits > fence); return bits % n; // Or using 32bit unsigned arithmetic avoiding modulus // Precompute final long fence = (1L << 32) % n; long result; do { // Compute 64bit unsigned product of n * [0, 2^32  1) result = n * (rng.nextInt() & 0xffffffffL); // Test the sample uniformity. } while ((result & 0xffffffffL) < fence); // Divide by 2^32 to get the sample return (int)(result >>> 32);
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.
0, 1, 2, ..., 0, 1, 2, ...
Algorithm 2 returns sample values in a linear order, e.g.
0, 0, 1, 1, 2, 2, ...
The suggested change is to implement smart precomputation in the DiscreteUniformSampler based on the range and use the algorithms that favour the most significant bits from the generator.
Attachments
Issue Links
 is related to

RNG90 Improve nextInt(int) and nextLong(long) for powers of 2
 Closed
 links to