You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2021/06/14 21:54:35 UTC
[commons-rng] branch master updated: RNG-145:
ContinuousUniformSampler to detect invalid open intervals.
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 898a874 RNG-145: ContinuousUniformSampler to detect invalid open intervals.
898a874 is described below
commit 898a8740c3aa47d7a892918e8379f46b17a2f175
Author: Alex Herbert <ah...@apache.org>
AuthorDate: Mon Jun 14 22:54:30 2021 +0100
RNG-145: ContinuousUniformSampler to detect invalid open intervals.
---
.../distribution/ContinuousUniformSampler.java | 77 +++++++++++++++--
.../distribution/ContinuousUniformSamplerTest.java | 96 +++++++++++++++++++++-
2 files changed, 166 insertions(+), 7 deletions(-)
diff --git a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ContinuousUniformSampler.java b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ContinuousUniformSampler.java
index e255062..48732b0 100644
--- a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ContinuousUniformSampler.java
+++ b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ContinuousUniformSampler.java
@@ -28,6 +28,11 @@ import org.apache.commons.rng.UniformRandomProvider;
public class ContinuousUniformSampler
extends SamplerBase
implements SharedStateContinuousSampler {
+ /** The minimum ULP gap for the open interval when the doubles have the same sign. */
+ private static final int MIN_ULP_SAME_SIGN = 2;
+ /** The minimum ULP gap for the open interval when the doubles have the opposite sign. */
+ private static final int MIN_ULP_OPPOSITE_SIGN = 3;
+
/** Lower bound. */
private final double lo;
/** Higher bound. */
@@ -138,21 +143,83 @@ public class ContinuousUniformSampler
/**
* Creates a new continuous uniform distribution sampler.
- * The bounds can be optionally excluded.
+ *
+ * <p>The bounds can be optionally excluded to sample from the open interval
+ * {@code (lower, upper)}. In this case if the bounds have the same sign the
+ * open interval must contain at least 1 double value between the limits; if the
+ * bounds have opposite signs the open interval must contain at least 2 double values
+ * between the limits excluding {@code -0.0}. Thus the interval {@code (-x,x)} will
+ * raise an exception when {@code x} is {@link Double#MIN_VALUE}.
*
* @param rng Generator of uniformly distributed random numbers.
* @param lo Lower bound.
* @param hi Higher bound.
- * @param excludeBounds Set to {@code true} to use the open interval {@code (lower, upper)}.
+ * @param excludeBounds Set to {@code true} to use the open interval
+ * {@code (lower, upper)}.
* @return the sampler
+ * @throws IllegalArgumentException If the open interval is invalid.
* @since 1.4
*/
public static SharedStateContinuousSampler of(UniformRandomProvider rng,
double lo,
double hi,
boolean excludeBounds) {
- return excludeBounds ?
- new OpenIntervalContinuousUniformSampler(rng, lo, hi) :
- new ContinuousUniformSampler(rng, lo, hi);
+ if (excludeBounds) {
+ if (!validateOpenInterval(lo, hi)) {
+ throw new IllegalArgumentException("Invalid open interval (" +
+ lo + "," + hi + ")");
+ }
+ return new OpenIntervalContinuousUniformSampler(rng, lo, hi);
+ }
+ return new ContinuousUniformSampler(rng, lo, hi);
+ }
+
+ /**
+ * Check that the open interval is valid. It must contain at least one double value
+ * between the limits if the signs are the same, or two double values between the limits
+ * if the signs are different (excluding {@code -0.0}).
+ *
+ * @param lo Lower bound.
+ * @param hi Higher bound.
+ * @return false is the interval is invalid
+ */
+ private static boolean validateOpenInterval(double lo, double hi) {
+ // Get the raw bit representation.
+ long bitsx = Double.doubleToRawLongBits(lo);
+ long bitsy = Double.doubleToRawLongBits(hi);
+ // xor will set the sign bit if the signs are different
+ if ((bitsx ^ bitsy) < 0) {
+ // Opposite signs. Drop the sign bit to represent the count of
+ // bits above +0.0. When combined this should be above 2.
+ // This prevents the range (-Double.MIN_VALUE, Double.MIN_VALUE)
+ // which cannot be sampled unless the uniform deviate u=0.5.
+ // (MAX_VALUE has all bits set except the most significant sign bit.)
+ bitsx &= Long.MAX_VALUE;
+ bitsy &= Long.MAX_VALUE;
+ if (lessThanUnsigned(bitsx + bitsy, MIN_ULP_OPPOSITE_SIGN)) {
+ return false;
+ }
+ } else {
+ // Same signs, subtraction will count the ULP difference.
+ // This should be above 1.
+ if (Math.abs(bitsx - bitsy) < MIN_ULP_SAME_SIGN) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Compares two {@code long} values numerically treating the values as unsigned
+ * to test if the first value is less than the second value.
+ *
+ * <p>See Long.compareUnsigned(long, long) in JDK 1.8.
+ *
+ * @param x the first value
+ * @param y the second value
+ * @return true if {@code x < y}
+ */
+ private static boolean lessThanUnsigned(long x, long y) {
+ return x + Long.MIN_VALUE < y + Long.MIN_VALUE;
}
}
diff --git a/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/ContinuousUniformSamplerTest.java b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/ContinuousUniformSamplerTest.java
index d937a98..76d56a4 100644
--- a/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/ContinuousUniformSamplerTest.java
+++ b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/ContinuousUniformSamplerTest.java
@@ -89,6 +89,79 @@ public class ContinuousUniformSamplerTest {
}
/**
+ * Test open intervals {@code (lower,upper)} where there are not enough double values
+ * between the limits.
+ */
+ @Test
+ public void testInvalidOpenIntervalThrows() {
+ final UniformRandomProvider rng = RandomSource.SPLIT_MIX_64.create(0);
+ for (final double[] interval : new double[][] {
+ // Opposite signs. Require two doubles inside the range.
+ {-0.0, 0.0},
+ {-0.0, Double.MIN_VALUE},
+ {-0.0, Double.MIN_VALUE * 2},
+ {-Double.MIN_VALUE, 0.0},
+ {-Double.MIN_VALUE * 2, 0.0},
+ {-Double.MIN_VALUE, Double.MIN_VALUE},
+ // Same signs. Requires one double inside the range.
+ // Same exponent
+ {1.23, Math.nextAfter(1.23, Double.POSITIVE_INFINITY)},
+ {1.23, Math.nextAfter(1.23, Double.NEGATIVE_INFINITY)},
+ // Different exponent
+ {2.0, Math.nextAfter(2.0, Double.NEGATIVE_INFINITY)},
+ }) {
+ final double low = interval[0];
+ final double high = interval[1];
+ try {
+ ContinuousUniformSampler.of(rng, low, high, true);
+ Assert.fail("(" + low + "," + high + ")");
+ } catch (IllegalArgumentException ex) {
+ // Expected
+ }
+ try {
+ ContinuousUniformSampler.of(rng, high, low, true);
+ Assert.fail("(" + high + "," + low + ")");
+ } catch (IllegalArgumentException ex) {
+ // Expected
+ }
+ }
+
+ // Valid. This will overflow if the raw long bits are extracted and
+ // subtracted to obtain a ULP difference.
+ ContinuousUniformSampler.of(rng, Double.MAX_VALUE, -Double.MAX_VALUE, true);
+ }
+
+ /**
+ * Test open intervals {@code (lower,upper)} where there is only the minimum number of
+ * double values between the limits.
+ */
+ @Test
+ public void testTinyOpenIntervalSample() {
+ final UniformRandomProvider rng = RandomSource.SPLIT_MIX_64.create(0);
+
+ // Test sub-normal ranges
+ final double x = Double.MIN_VALUE;
+
+ for (final double expected : new double[] {
+ 1.23, 2, 56787.7893, 3 * x, 2 * x, x
+ }) {
+ final double low = Math.nextAfter(expected, Double.POSITIVE_INFINITY);
+ final double high = Math.nextAfter(expected, Double.NEGATIVE_INFINITY);
+ Assert.assertEquals(expected, ContinuousUniformSampler.of(rng, low, high, true).sample(), 0.0);
+ Assert.assertEquals(expected, ContinuousUniformSampler.of(rng, high, low, true).sample(), 0.0);
+ Assert.assertEquals(-expected, ContinuousUniformSampler.of(rng, -low, -high, true).sample(), 0.0);
+ Assert.assertEquals(-expected, ContinuousUniformSampler.of(rng, -high, -low, true).sample(), 0.0);
+ }
+
+ // Special case of sampling around zero.
+ // Requires 2 doubles inside the range.
+ final double y = ContinuousUniformSampler.of(rng, -x, 2 * x, true).sample();
+ Assert.assertTrue(-x < y && y < 2 * x);
+ final double z = ContinuousUniformSampler.of(rng, -2 * x, x, true).sample();
+ Assert.assertTrue(-2 * x < z && z < x);
+ }
+
+ /**
* Test the SharedStateSampler implementation.
*/
@Test
@@ -103,8 +176,27 @@ public class ContinuousUniformSamplerTest {
* @param excludedBounds Set to true to exclude the bounds.
*/
private static void testSharedStateSampler(boolean excludedBounds) {
- final UniformRandomProvider rng1 = RandomSource.SPLIT_MIX_64.create(0L);
- final UniformRandomProvider rng2 = RandomSource.SPLIT_MIX_64.create(0L);
+ // Create RNGs that will generate a sample at the limits.
+ // This tests the bounds excluded sampler correctly shares state.
+ // Do this using a RNG that outputs 0 for the first nextDouble().
+ final UniformRandomProvider rng1 = new SplitMix64(0L) {
+ private double x;
+ @Override
+ public double nextDouble() {
+ final double y = x;
+ x = super.nextDouble();
+ return y;
+ }
+ };
+ final UniformRandomProvider rng2 = new SplitMix64(0L) {
+ private double x;
+ @Override
+ public double nextDouble() {
+ final double y = x;
+ x = super.nextDouble();
+ return y;
+ }
+ };
final double low = 1.23;
final double high = 4.56;
final SharedStateContinuousSampler sampler1 =