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 2022/03/18 14:47:40 UTC
[commons-rng] branch master updated: RNG-172: Pre-compute rejection threshold
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 994616f RNG-172: Pre-compute rejection threshold
994616f is described below
commit 994616fa38039c295535f24b5242bf0a7f5b0ead
Author: aherbert <ah...@apache.org>
AuthorDate: Fri Mar 18 14:46:48 2022 +0000
RNG-172: Pre-compute rejection threshold
---
.../sampling/distribution/UniformLongSampler.java | 51 ++++++++++++++++-----
.../distribution/UniformLongSamplerTest.java | 52 +++++++++++++++++-----
src/changes/changes.xml | 3 ++
3 files changed, 83 insertions(+), 23 deletions(-)
diff --git a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/UniformLongSampler.java b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/UniformLongSampler.java
index 28766ac..cdd5ee7 100644
--- a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/UniformLongSampler.java
+++ b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/UniformLongSampler.java
@@ -115,36 +115,63 @@ public abstract class UniformLongSampler implements SharedStateLongSampler {
/**
* Discrete uniform distribution sampler when the range is small
- * enough to fit in a positive long.
+ * enough to fit in a positive long. The range must not be a power of 2.
* This sampler assumes the lower bound of the range is 0.
*/
private static class SmallRangeUniformLongSampler extends UniformLongSampler {
/** Maximum range of the sample (exclusive). */
private final long n;
+ /** Limit of the uniform range (exclusive). This is the largest positive
+ * multiple of {@code n}. */
+ private final long limit;
/**
* @param rng Generator of uniformly distributed random numbers.
* @param range Maximum range of the sample (exclusive).
+ * Must not be a power of 2.
*/
SmallRangeUniformLongSampler(UniformRandomProvider rng,
long range) {
super(rng);
this.n = range;
+ // Set the upper limit for the positive long.
+ // The sample must be selected from the largest multiple
+ // of range that fits within a positive value:
+ // limit = floor(2^63 / range) * range
+ // = 2^63 - (2^63 % range)
+ // This is a one-off computation cost.
+ // The divide will truncate towards zero (do not use Math.floorDiv).
+ // Note: This is invalid if range is a power of 2 as it fits exactly in 2^63
+ // and the limit is computed as 2^63 (not representable).
+ // This is not possible here as this sampler is used for non-powers of 2.
+ limit = (Long.MIN_VALUE / range) * -range;
+ }
+
+ /**
+ * @param rng Generator of uniformly distributed random numbers.
+ * @param source Source to copy.
+ */
+ SmallRangeUniformLongSampler(UniformRandomProvider rng,
+ SmallRangeUniformLongSampler source) {
+ super(rng);
+ this.n = source.n;
+ this.limit = source.limit;
}
@Override
public long sample() {
- // Rejection algorithm copied from o.a.c.rng.core.BaseProvider
- // to avoid the (n <= 0) conditional.
- // See the JDK javadoc for java.util.Random.nextInt(int) for
- // a description of the algorithm.
- long bits;
- long val;
- do {
- bits = rng.nextLong() >>> 1;
- val = bits % n;
- } while (bits - val + (n - 1) < 0);
- return val;
+ // Note:
+ // This will have the same output as the rejection algorithm
+ // from o.a.c.rng.core.BaseProvider. The limit for the uniform
+ // positive value can be pre-computed. This ensures exactly
+ // 1 modulus operation per call.
+ for (;;) {
+ // bits in [0, limit)
+ final long bits = rng.nextLong() >>> 1;
+ if (bits < limit) {
+ return bits % n;
+ }
+ }
}
@Override
diff --git a/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/UniformLongSamplerTest.java b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/UniformLongSamplerTest.java
index 3fb6216..802a018 100644
--- a/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/UniformLongSamplerTest.java
+++ b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/UniformLongSamplerTest.java
@@ -23,7 +23,8 @@ import org.apache.commons.rng.sampling.RandomAssert;
import org.apache.commons.rng.simple.RandomSource;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
-
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ValueSource;
import java.util.Locale;
/**
@@ -84,32 +85,61 @@ class UniformLongSamplerTest {
* based on o.a.c.rng.core.BaseProvider as the rejection algorithm is
* the same.
*/
- @Test
- void testSamplesWithSmallNonPowerOf2Range() {
- final long upper = 234293789329234L;
+ @ParameterizedTest
+ @ValueSource(longs = {234293789329234L, 145, 69987, 12673586268L, 234785389445435L, Long.MAX_VALUE})
+ void testSamplesWithSmallNonPowerOf2Range(long upper) {
for (final long lower : new long[] {-13, 0, 13}) {
final long n = upper - lower + 1;
- // Use an RNG that forces the rejection path on the first sample
- final UniformRandomProvider rng1 = createRngWithFullBitsOnFirstCall();
- final UniformRandomProvider rng2 = createRngWithFullBitsOnFirstCall();
+ // Skip overflow ranges
+ if (n < 0) {
+ continue;
+ }
+
+ Assertions.assertNotEquals(0, n & (n - 1), "Power of 2 is invalid here");
+
+ // Largest multiple of the upper bound.
+ // floor(2^63 / range) * range
+ // Computed as 2^63 - 2 % 63 with unsigned integers.
+ final long m = Long.MIN_VALUE - Long.remainderUnsigned(Long.MIN_VALUE, n);
+
+ // Check the method used in the sampler
+ Assertions.assertEquals(m, (Long.MIN_VALUE / n) * -n);
+
+ // Use an RNG that forces the rejection path on the first few samples
+ // This occurs when the positive value is above the limit set by the
+ // largest multiple of upper that does not overflow.
+ final UniformRandomProvider rng1 = createRngWithFullBitsOnFirstCall(m);
+ final UniformRandomProvider rng2 = createRngWithFullBitsOnFirstCall(m);
final UniformLongSampler sampler = UniformLongSampler.of(rng2, lower, upper);
- for (int i = 0; i < 10; i++) {
+ for (int i = 0; i < 100; i++) {
Assertions.assertEquals(lower + rng1.nextLong(n), sampler.sample());
}
}
}
/**
- * Creates a RNG which will return full bits for the first sample.
+ * Creates a RNG which will return full bits for the first sample, then bits
+ * too high for the configured limit for a few iterations.
*
+ * @param m Upper limit for a sample
* @return the uniform random provider
*/
- private static UniformRandomProvider createRngWithFullBitsOnFirstCall() {
+ private static UniformRandomProvider createRngWithFullBitsOnFirstCall(long m) {
return new SplitMix64(0L) {
private int i;
@Override
public long next() {
- return i++ == 0 ? -1L : super.next();
+ int j = i++;
+ if (j == 0) {
+ // Full bits
+ return -1L;
+ } else if (j < 6) {
+ // A value just above or below the limit.
+ // Assumes m is positive and the sampler uses >>> 1 to extract
+ // a positive value.
+ return (m + 3 - j) << 1;
+ }
+ return super.next();
}
};
}
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index d7224d2..598e1fe 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -81,6 +81,9 @@ 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="update" issue="172">
+ "UniformLongSampler": Precompute rejection threshold for a non-power of 2 range.
+ </action>
<action dev="aherbert" type="update" issue="169">
"RandomSource.create": Update array seed conversion to use optimum seed length.
Avoid duplication of input bytes and conversion of bytes that will be discarded.