[RNG-144] AhrensDieterExponentialSampler can infinite loop

• Type: Bug
• Status: Closed
• Priority: Minor
• Resolution: Fixed
• Affects Version/s: 1.3
• Fix Version/s: 1.4
• Component/s: sampling
• Assignee: Unassigned
• Reporter: Alex Herbert
• Created: 10/Jun/21 23:34
• Updated: 13/Sep/21 10:41
• Resolved: 11/Jun/21 12:07

Description

If the RNG provides a value of 0 for a uniform deviate the sampler will infinite loop. Here is the initial part of the sample method:

public double sample() {
    // Step 1:
    double a = 0;
    // *** u can be zero ***
    double u = rng.nextDouble();

    // Step 2 and 3:
    while (u < 0.5) {
        a += EXPONENTIAL_SA_QI[0];
        // *** u is always zero => infinite loop ***
        u *= 2;
    }

The origin of the method is not stated in the source; the reference from the original source in Commons Math 3 is to a dead link. A brief search did not find a reference with this method.

It is assumed the variable u should be in the open interval (0, 1), not the interval [0, 1) typically provided by a RNG supplying the 2^53 dyadic rationals in the interval 0 to 1.

This can be fixed by using an open interval or changing the interval to (0, 1]:

double nextDouble() {
    // A value in [0, 1)
    double x = rng.nextDouble();
    // recursion if zero
    return x == 0 ? nextDouble() : x;
}

double nextDouble() {
    // A value in (0, 1].
    return 0x1.0p-53 * ((rng.nextLong() >>> 11) + 1L);
}

Either method fixes this test:

@Test
public void testSamplerWithZeroFromFirstRandomDeviate() {
    // Create a zero for the first call to the sampler, then non-zero after
    final UniformRandomProvider rng = new SplitMix64(0) {
        private long l = 0;
        @Override
        public long nextLong() { return l++; }
    };
    final SharedStateContinuousSampler sampler =
            AhrensDieterExponentialSampler.of(rng, 1);
    // Infinite loop
    sampler.sample();
}