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 <aherb...@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 =