[RNG-172] UniformLongSampler can precompute the rejection limit

• Type: Improvement
• Status: Closed
• Priority: Trivial
• Resolution: Implemented
• Affects Version/s: 1.4
• Fix Version/s: 1.5
• Component/s: sampling
• Assignee: Unassigned
• Reporter: Alex Herbert
• Created: 18/Mar/22 14:13
• Updated: 10/Oct/22 11:54
• Resolved: 18/Mar/22 14:48

Description

The UniformLongSampler uses this rejection algorithm for non-powers of 2 range 'n':

@Override
public long sample() {
    // Rejection algorithm copied from o.a.c.rng.core.BaseProvider
    // to avoid the (n <= 0) conditional.
    // See the JDK javadoc for java.util.Random.nextInt(int) for
    // a description of the algorithm.
    long bits;
    long val;
    do {
        bits = rng.nextLong() >>> 1;
        val  = bits % n;
    } while (bits - val + (n - 1) < 0);
    return val;
}

This requires a modulus operation per iteration. Worst case expected iteration of the loop is 2 times and thus 2 modulus calls.

However the statement while (bits - val + (n - 1) < 0) is checking if the bits came from the range [0, limit) where limit is the largest multiple of n that is a positive value. Essential the bits must uniformly be picked from a range that can be used with modulus n and still be uniform for all values.

This limit can be precomputed and the sampling loop changed to have 1 modulus call:

@Override
public long sample() {
    // Note:
    // This will have the same output as the rejection algorithm
    // from o.a.c.rng.core.BaseProvider. The limit for the uniform
    // positive value can be pre-computed. This ensures exactly
    // 1 modulus operation per call.
    long bits = rng.nextLong() >>> 1;
    while (bits >= limit) {
        bits = rng.nextLong() >>> 1;
    }
    return bits % n;
}

This does not work if the range n is a power of 2 as the limit is 2^63 and no sample for bits can be above it. This sampler uses a different method for power of 2 range and so the limit can be precomputed as used here.

The output from the sampler will be the same.