[jira] [Resolved] (RNG-144) AhrensDieterExponentialSampler can infinite loop

["Alex Herbert (Jira)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/RNG-144?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Alex Herbert resolved RNG-144.
------------------------------
    Fix Version/s: 1.4
       Resolution: Fixed

Resolved by creating the first uniform deviate in the interval {{(0, 1]}}, i.e. non-zero. If the first uniform deviate is 1 the method creates a valid sample.

The rest of the sample method is robust to zeros from the underlying generator nextDouble() method.

Fixed in commits:

585e205cb3266c6fc3074699946a080c61aa5c3e

c7779b1e32ce3533d2f9f440b46106bb1907be46

 

> AhrensDieterExponentialSampler can infinite loop
> ------------------------------------------------
>
>                 Key: RNG-144
>                 URL: https://issues.apache.org/jira/browse/RNG-144
>             Project: Commons RNG
>          Issue Type: Bug
>          Components: sampling
>    Affects Versions: 1.3
>            Reporter: Alex Herbert
>            Priority: Minor
>             Fix For: 1.4
>
>
> 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:
> {code:java}
> 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;
>     }
> {code}
> 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]:
> {code:java}
> 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);
> }
> {code}
> Either method fixes this test:
> {code:java}
> @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();
> }
> {code}



--
This message was sent by Atlassian Jira
(v8.3.4#803005)