This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git
The following commit(s) were added to refs/heads/master by this push:
new 585e205 RNG-144: AhrensDieterExponentialSampler to avoid an infinite
loop
585e205 is described below
commit 585e205cb3266c6fc3074699946a080c61aa5c3e
Author: aherbert <aherb...@apache.org>
AuthorDate: Fri Jun 11 12:54:50 2021 +0100
RNG-144: AhrensDieterExponentialSampler to avoid an infinite loop
---
.../AhrensDieterExponentialSampler.java | 26 +++++++++++++++++++--
.../AhrensDieterExponentialSamplerTest.java | 27 ++++++++++++++++++++++
src/changes/changes.xml | 4 ++++
3 files changed, 55 insertions(+), 2 deletions(-)
diff --git
a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/AhrensDieterExponentialSampler.java
b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/AhrensDieterExponentialSampler.java
index 6ae1850..702ecf7 100644
---
a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/AhrensDieterExponentialSampler.java
+++
b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/AhrensDieterExponentialSampler.java
@@ -21,7 +21,12 @@ import org.apache.commons.rng.UniformRandomProvider;
/**
* Sampling from an <a
href="http://mathworld.wolfram.com/ExponentialDistribution.html";>exponential
distribution</a>.
*
- * <p>Sampling uses {@link UniformRandomProvider#nextDouble()}.</p>
+ * <p>Sampling uses:</p>
+ *
+ * <ul>
+ * <li>{@link UniformRandomProvider#nextLong()}
+ * <li>{@link UniformRandomProvider#nextDouble()}
+ * </ul>
*
* @since 1.0
*/
@@ -41,6 +46,11 @@ public class AhrensDieterExponentialSampler
* By trying, n = 16 in Java is enough to reach 1.
*/
private static final double[] EXPONENTIAL_SA_QI = new double[16];
+ /**
+ * The multiplier to convert the least significant 53-bits of a {@code
long} to a {@code double}.
+ * Taken from org.apache.commons.rng.core.util.NumberFactory.
+ */
+ private static final double DOUBLE_MULTIPLIER = 0x1.0p-53d;
/** The mean of this distribution. */
private final double mean;
/** Underlying source of randomness. */
@@ -94,7 +104,8 @@ public class AhrensDieterExponentialSampler
public double sample() {
// Step 1:
double a = 0;
- double u = rng.nextDouble();
+ // Avoid u=0 which creates an infinite loop
+ double u = nextNonZeroDouble();
// Step 2 and 3:
while (u < 0.5) {
@@ -130,6 +141,17 @@ public class AhrensDieterExponentialSampler
return mean * (a + umin * EXPONENTIAL_SA_QI[0]);
}
+ /**
+ * Create a double in the interval {@code (0, 1]}.
+ *
+ * @return a {@code double} value in the interval {@code (0, 1]}.
+ */
+ private double nextNonZeroDouble() {
+ // This matches the method in
o.a.c.rng.core.util.NumberFactory.makeDouble(long)
+ // but shifts the range from [0, 1) to (0, 1].
+ return ((rng.nextLong() >>> 11) + 1L) * DOUBLE_MULTIPLIER;
+ }
+
/** {@inheritDoc} */
@Override
public String toString() {
diff --git
a/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/AhrensDieterExponentialSamplerTest.java
b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/AhrensDieterExponentialSamplerTest.java
index de771b6..d7b81a8 100644
---
a/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/AhrensDieterExponentialSamplerTest.java
+++
b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/AhrensDieterExponentialSamplerTest.java
@@ -16,16 +16,25 @@
*/
package org.apache.commons.rng.sampling.distribution;
+import java.util.concurrent.TimeUnit;
import org.apache.commons.rng.RestorableUniformRandomProvider;
import org.apache.commons.rng.UniformRandomProvider;
+import org.apache.commons.rng.core.source64.SplitMix64;
import org.apache.commons.rng.sampling.RandomAssert;
import org.apache.commons.rng.simple.RandomSource;
+import org.junit.Rule;
import org.junit.Test;
+import org.junit.rules.Timeout;
/**
* Test for the {@link AhrensDieterExponentialSampler}. The tests hit edge
cases for the sampler.
*/
public class AhrensDieterExponentialSamplerTest {
+
+ /** The global timeout for tests. Used to kill a test stuck in an infinite
loop. */
+ @Rule
+ public Timeout globalTimeout = new Timeout(50, TimeUnit.MILLISECONDS);
+
/**
* Test the constructor with a bad mean.
*/
@@ -50,4 +59,22 @@ public class AhrensDieterExponentialSamplerTest {
final SharedStateContinuousSampler sampler2 =
sampler1.withUniformRandomProvider(rng2);
RandomAssert.assertProduceSameSequence(sampler1, sampler2);
}
+
+ /**
+ * Test the sampler is robust to a generator that outputs zeros.
+ * See RNG-144.
+ */
+ @Test
+ public void testSamplerWithZeroFromRandomGenerator() {
+ // A broken generator that returns zero.
+ final UniformRandomProvider rng = new SplitMix64(0) {
+ @Override
+ public long nextLong() {
+ return 0L;
+ }
+ };
+ final SharedStateContinuousSampler sampler =
AhrensDieterExponentialSampler.of(rng, 1);
+ // This should not infinite loop
+ sampler.sample();
+ }
}
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 64b5231..b603c09 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -77,6 +77,10 @@ re-run tests that fail, and pass the build if they succeed
within the allotted number of reruns (the test will be marked
as 'flaky' in the report).
">
+ <action dev="aherbert" type="fix" issue="144">
+ "AhrensDieterExponentialSampler": Avoid possible infinite loop during
sampling if the
+ underlying UniformRandomProvider creates a zero for the uniform
deviate.
+ </action>
<action dev="aherbert" type="add" issue="143">
"RandomSource": Add an instance create method. Deprecate the static
create method.
</action>
