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/09/19 19:10:50 UTC
[commons-rng] 01/03: RNG-181: LXM family to support SplittableUniformRandomProvider
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
commit 0021eb92a56dd5dc61e63256fb2a30c316c7d8af
Author: Alex Herbert <ah...@apache.org>
AuthorDate: Wed Sep 7 13:08:56 2022 +0100
RNG-181: LXM family to support SplittableUniformRandomProvider
Create generic RandomStreams class that can stream objects created with
a seed and splittable source of randomness. The seed uses the stream
position mixed with random bits to ensure it is unique within the stream
(up to a size limit of 2^60). Use this feature to support splits in the
LXM family.
Add isSplittable method to RandomSource to use to identify supported
interfaces.
Use of the splittable interface by other modules requires an exception
in RevAPI for exposing an external class in the API. This is similar to
exposure of UniformRandomProvider and is allowed. The change is
non-breaking for binary and source compatibility (see revapi
java.class.externalClassExposedInAPI).
---
.../org/apache/commons/rng/core/BaseProvider.java | 8 +-
.../commons/rng/core/source32/L32X64Mix.java | 51 ++-
.../commons/rng/core/source32/LXMSupport.java | 8 +
.../commons/rng/core/source64/L128X1024Mix.java | 60 ++-
.../commons/rng/core/source64/L128X128Mix.java | 52 ++-
.../commons/rng/core/source64/L128X256Mix.java | 57 ++-
.../commons/rng/core/source64/L64X1024Mix.java | 60 ++-
.../commons/rng/core/source64/L64X128Mix.java | 51 ++-
.../commons/rng/core/source64/L64X128StarStar.java | 43 +-
.../commons/rng/core/source64/L64X256Mix.java | 54 ++-
.../commons/rng/core/source64/LXMSupport.java | 8 +
.../commons/rng/core/util/RandomStreams.java | 278 +++++++++++++
.../org/apache/commons/rng/core/ProvidersList.java | 18 +-
.../org/apache/commons/rng/core/RandomAssert.java | 34 ++
.../core/SplittableProvidersParametricTest.java | 359 +++++++++++++++++
.../commons/rng/core/source32/L32X64MixTest.java | 28 ++
.../rng/core/source64/L128X1024MixTest.java | 29 ++
.../commons/rng/core/source64/L128X128MixTest.java | 28 ++
.../commons/rng/core/source64/L128X256MixTest.java | 28 ++
.../commons/rng/core/source64/L64X1024MixTest.java | 29 ++
.../commons/rng/core/source64/L64X128MixTest.java | 28 ++
.../rng/core/source64/L64X128StarStarTest.java | 28 ++
.../commons/rng/core/source64/L64X256MixTest.java | 28 ++
.../commons/rng/core/util/RandomStreamsTest.java | 448 +++++++++++++++++++++
.../rng/core/util/RandomStreamsTestHelper.java | 39 ++
.../apache/commons/rng/simple/RandomSource.java | 23 ++
.../rng/simple/ProvidersCommonParametricTest.java | 4 +
.../commons/rng/simple/RandomSourceTest.java | 7 +
src/main/resources/pmd/pmd-ruleset.xml | 10 +-
src/main/resources/revapi/api-changes.json | 6 +
30 files changed, 1892 insertions(+), 12 deletions(-)
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/BaseProvider.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/BaseProvider.java
index e78dbea2..164258fa 100644
--- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/BaseProvider.java
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/BaseProvider.java
@@ -404,9 +404,12 @@ public abstract class BaseProvider
*
* <p>This is ranked first of the top 14 Stafford mixers.
*
+ * <p>This function can be used to mix the bits of a {@code long} value to
+ * obtain a better distribution and avoid collisions between similar values.
+ *
* @param x the input value
* @return the output value
- * @see <a href="http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html">Better
+ * @see <a href="https://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html">Better
* Bit Mixing - Improving on MurmurHash3's 64-bit Finalizer.</a>
*/
private static long stafford13(long x) {
@@ -418,6 +421,9 @@ public abstract class BaseProvider
/**
* Perform the finalising 32-bit mix function of Austin Appleby's MurmurHash3.
*
+ * <p>This function can be used to mix the bits of a {@code int} value to
+ * obtain a better distribution and avoid collisions between similar values.
+ *
* @param x the input value
* @return the output value
* @see <a href="https://github.com/aappleby/smhasher">SMHasher</a>
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/L32X64Mix.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/L32X64Mix.java
index 19c6b982..cb21433f 100644
--- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/L32X64Mix.java
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/L32X64Mix.java
@@ -17,10 +17,13 @@
package org.apache.commons.rng.core.source32;
+import java.util.stream.Stream;
import org.apache.commons.rng.JumpableUniformRandomProvider;
import org.apache.commons.rng.LongJumpableUniformRandomProvider;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.core.util.NumberFactory;
+import org.apache.commons.rng.core.util.RandomStreams;
/**
* A 32-bit all purpose generator.
@@ -41,13 +44,22 @@ import org.apache.commons.rng.core.util.NumberFactory;
* against accidental correlation in a multi-threaded setting. The additive parameters must be
* different in the most significant 31-bits.
*
+ * <p>This generator implements
+ * {@link org.apache.commons.rng.SplittableUniformRandomProvider SplittableUniformRandomProvider}.
+ * The stream of generators created using the {@code splits} methods support parallelisation
+ * and are robust against accidental correlation by using unique values for the additive parameter
+ * for each instance in the same stream. The primitive streaming methods support parallelisation
+ * but with no assurances of accidental correlation; each thread uses a new instance with a
+ * randomly initialised state.
+ *
* @see <a href="https://doi.org/10.1145/3485525">Steele & Vigna (2021) Proc. ACM Programming
* Languages 5, 1-31</a>
* @see <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/random/package-summary.html">
* JDK 17 java.util.random javadoc</a>
* @since 1.5
*/
-public final class L32X64Mix extends IntProvider implements LongJumpableUniformRandomProvider {
+public final class L32X64Mix extends IntProvider implements LongJumpableUniformRandomProvider,
+ SplittableUniformRandomProvider {
// Implementation note:
// This does not extend AbstractXoRoShiRo64 as the XBG function is re-implemented
// inline to allow parallel pipelining. Inheritance would provide only the XBG state.
@@ -213,4 +225,41 @@ public final class L32X64Mix extends IntProvider implements LongJumpableUniformR
resetCachedState();
return copy;
}
+
+ /** {@inheritDoc} */
+ @Override
+ public SplittableUniformRandomProvider split(UniformRandomProvider source) {
+ // The upper half of the long seed is discarded so use nextInt
+ return create(source.nextInt(), source);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Stream<SplittableUniformRandomProvider> splits(long streamSize, SplittableUniformRandomProvider source) {
+ return RandomStreams.generateWithSeed(streamSize, source, L32X64Mix::create);
+ }
+
+ /**
+ * Create a new instance using the given {@code seed} and {@code source} of randomness
+ * to initialise the instance.
+ *
+ * @param seed Seed used to initialise the instance.
+ * @param source Source of randomness used to initialise the instance.
+ * @return A new instance.
+ */
+ private static SplittableUniformRandomProvider create(long seed, UniformRandomProvider source) {
+ // LCG state. The addition uses the input seed.
+ // The LCG addition parameter is set to odd so left-shift the seed.
+ final int s0 = (int) seed << 1;
+ final int s1 = source.nextInt();
+ // XBG state must not be all zero
+ int x0 = source.nextInt();
+ int x1 = source.nextInt();
+ if ((x0 | x1) == 0) {
+ // SplitMix style seed ensures at least one non-zero value
+ x0 = LXMSupport.lea32(s1);
+ x1 = LXMSupport.lea32(s1 + LXMSupport.GOLDEN_RATIO_32);
+ }
+ return new L32X64Mix(s0, s1, x0, x1);
+ }
}
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/LXMSupport.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/LXMSupport.java
index 290bb3d9..94e893c8 100644
--- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/LXMSupport.java
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/LXMSupport.java
@@ -48,6 +48,14 @@ final class LXMSupport {
* </pre>
*/
static final int C32P = 0x046b0000;
+ /**
+ * The fractional part of the golden ratio, phi, scaled to 32-bits and rounded to odd.
+ * <pre>
+ * phi = (sqrt(5) - 1) / 2) * 2^32
+ * </pre>
+ * @see <a href="https://en.wikipedia.org/wiki/Golden_ratio">Golden ratio</a>
+ */
+ static final int GOLDEN_RATIO_32 = 0x9e3779b9;
/** No instances. */
private LXMSupport() {}
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L128X1024Mix.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L128X1024Mix.java
index 0417026c..d9bdeabf 100644
--- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L128X1024Mix.java
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L128X1024Mix.java
@@ -17,9 +17,12 @@
package org.apache.commons.rng.core.source64;
+import java.util.stream.Stream;
import org.apache.commons.rng.JumpableUniformRandomProvider;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.core.util.NumberFactory;
+import org.apache.commons.rng.core.util.RandomStreams;
/**
* A 64-bit all purpose generator.
@@ -41,17 +44,27 @@ import org.apache.commons.rng.core.util.NumberFactory;
* against accidental correlation in a multi-threaded setting. The additive parameters must be
* different in the most significant 127-bits.
*
+ * <p>This generator implements
+ * {@link org.apache.commons.rng.SplittableUniformRandomProvider SplittableUniformRandomProvider}.
+ * The stream of generators created using the {@code splits} methods support parallelisation
+ * and are robust against accidental correlation by using unique values for the additive parameter
+ * for each instance in the same stream. The primitive streaming methods support parallelisation
+ * but with no assurances of accidental correlation; each thread uses a new instance with a
+ * randomly initialised state.
+ *
* @see <a href="https://doi.org/10.1145/3485525">Steele & Vigna (2021) Proc. ACM Programming
* Languages 5, 1-31</a>
* @see <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/random/package-summary.html">
* JDK 17 java.util.random javadoc</a>
* @since 1.5
*/
-public class L128X1024Mix extends AbstractL128 {
+public class L128X1024Mix extends AbstractL128 implements SplittableUniformRandomProvider {
/** Size of the seed vector. */
private static final int SEED_SIZE = 20;
/** Size of the XBG state vector. */
private static final int XBG_STATE_SIZE = 16;
+ /** Size of the LCG state vector. */
+ private static final int LCG_STATE_SIZE = SEED_SIZE - XBG_STATE_SIZE;
/** Low half of 128-bit LCG multiplier. */
private static final long ML = LXMSupport.M128L;
@@ -185,4 +198,49 @@ public class L128X1024Mix extends AbstractL128 {
// the correct class type. It should not be public.
return new L128X1024Mix(this);
}
+
+ /** {@inheritDoc} */
+ @Override
+ public SplittableUniformRandomProvider split(UniformRandomProvider source) {
+ return create(source.nextLong(), source);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Stream<SplittableUniformRandomProvider> splits(long streamSize, SplittableUniformRandomProvider source) {
+ return RandomStreams.generateWithSeed(streamSize, source, L128X1024Mix::create);
+ }
+
+ /**
+ * Create a new instance using the given {@code seed} and {@code source} of randomness
+ * to initialise the instance.
+ *
+ * @param seed Seed used to initialise the instance.
+ * @param source Source of randomness used to initialise the instance.
+ * @return A new instance.
+ */
+ private static SplittableUniformRandomProvider create(long seed, UniformRandomProvider source) {
+ final long[] s = new long[SEED_SIZE];
+ // LCG state. The addition lower-half uses the input seed.
+ // The LCG addition parameter is set to odd so left-shift the seed.
+ s[0] = source.nextLong();
+ s[1] = seed << 1;
+ s[2] = source.nextLong();
+ s[3] = source.nextLong();
+ // XBG state must not be all zero
+ long x = 0;
+ for (int i = LCG_STATE_SIZE; i < s.length; i++) {
+ s[i] = source.nextLong();
+ x |= s[i];
+ }
+ if (x == 0) {
+ // SplitMix style seed ensures at least one non-zero value
+ x = s[LCG_STATE_SIZE - 1];
+ for (int i = LCG_STATE_SIZE; i < s.length; i++) {
+ s[i] = LXMSupport.lea64(x);
+ x += LXMSupport.GOLDEN_RATIO_64;
+ }
+ }
+ return new L128X1024Mix(s);
+ }
}
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L128X128Mix.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L128X128Mix.java
index 8d905f24..8938ba52 100644
--- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L128X128Mix.java
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L128X128Mix.java
@@ -17,9 +17,12 @@
package org.apache.commons.rng.core.source64;
+import java.util.stream.Stream;
import org.apache.commons.rng.JumpableUniformRandomProvider;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.core.util.NumberFactory;
+import org.apache.commons.rng.core.util.RandomStreams;
/**
* A 64-bit all purpose generator.
@@ -41,13 +44,21 @@ import org.apache.commons.rng.core.util.NumberFactory;
* against accidental correlation in a multi-threaded setting. The additive parameters must be
* different in the most significant 127-bits.
*
+ * <p>This generator implements
+ * {@link org.apache.commons.rng.SplittableUniformRandomProvider SplittableUniformRandomProvider}.
+ * The stream of generators created using the {@code splits} methods support parallelisation
+ * and are robust against accidental correlation by using unique values for the additive parameter
+ * for each instance in the same stream. The primitive streaming methods support parallelisation
+ * but with no assurances of accidental correlation; each thread uses a new instance with a
+ * randomly initialised state.
+ *
* @see <a href="https://doi.org/10.1145/3485525">Steele & Vigna (2021) Proc. ACM Programming
* Languages 5, 1-31</a>
* @see <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/random/package-summary.html">
* JDK 17 java.util.random javadoc</a>
* @since 1.5
*/
-public class L128X128Mix extends AbstractL128 {
+public class L128X128Mix extends AbstractL128 implements SplittableUniformRandomProvider {
/** Size of the seed vector. */
private static final int SEED_SIZE = 6;
/** Size of the XBG state vector. */
@@ -202,4 +213,43 @@ public class L128X128Mix extends AbstractL128 {
// the correct class type. It should not be public.
return new L128X128Mix(this);
}
+
+ /** {@inheritDoc} */
+ @Override
+ public SplittableUniformRandomProvider split(UniformRandomProvider source) {
+ return create(source.nextLong(), source);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Stream<SplittableUniformRandomProvider> splits(long streamSize, SplittableUniformRandomProvider source) {
+ return RandomStreams.generateWithSeed(streamSize, source, L128X128Mix::create);
+ }
+
+ /**
+ * Create a new instance using the given {@code seed} and {@code source} of randomness
+ * to initialise the instance.
+ *
+ * @param seed Seed used to initialise the instance.
+ * @param source Source of randomness used to initialise the instance.
+ * @return A new instance.
+ */
+ private static SplittableUniformRandomProvider create(long seed, UniformRandomProvider source) {
+ // LCG state. The addition lower-half uses the input seed.
+ // The LCG addition parameter is set to odd so left-shift the seed.
+ final long s0 = source.nextLong();
+ final long s1 = seed << 1;
+ final long s2 = source.nextLong();
+ final long s3 = source.nextLong();
+ // XBG state must not be all zero
+ long x0 = source.nextLong();
+ long x1 = source.nextLong();
+ if ((x0 | x1) == 0) {
+ // SplitMix style seed ensures at least one non-zero value
+ final long z = s3;
+ x0 = LXMSupport.lea64(z);
+ x1 = LXMSupport.lea64(z + LXMSupport.GOLDEN_RATIO_64);
+ }
+ return new L128X128Mix(s0, s1, s2, s3, x0, x1);
+ }
}
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L128X256Mix.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L128X256Mix.java
index 16a1b0a3..c860b429 100644
--- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L128X256Mix.java
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L128X256Mix.java
@@ -17,9 +17,12 @@
package org.apache.commons.rng.core.source64;
+import java.util.stream.Stream;
import org.apache.commons.rng.JumpableUniformRandomProvider;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.core.util.NumberFactory;
+import org.apache.commons.rng.core.util.RandomStreams;
/**
* A 64-bit all purpose generator.
@@ -41,13 +44,21 @@ import org.apache.commons.rng.core.util.NumberFactory;
* against accidental correlation in a multi-threaded setting. The additive parameters must be
* different in the most significant 127-bits.
*
+ * <p>This generator implements
+ * {@link org.apache.commons.rng.SplittableUniformRandomProvider SplittableUniformRandomProvider}.
+ * The stream of generators created using the {@code splits} methods support parallelisation
+ * and are robust against accidental correlation by using unique values for the additive parameter
+ * for each instance in the same stream. The primitive streaming methods support parallelisation
+ * but with no assurances of accidental correlation; each thread uses a new instance with a
+ * randomly initialised state.
+ *
* @see <a href="https://doi.org/10.1145/3485525">Steele & Vigna (2021) Proc. ACM Programming
* Languages 5, 1-31</a>
* @see <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/random/package-summary.html">
* JDK 17 java.util.random javadoc</a>
* @since 1.5
*/
-public class L128X256Mix extends AbstractL128 {
+public class L128X256Mix extends AbstractL128 implements SplittableUniformRandomProvider {
/** Size of the seed vector. */
private static final int SEED_SIZE = 8;
/** Size of the XBG state vector. */
@@ -230,4 +241,48 @@ public class L128X256Mix extends AbstractL128 {
// the correct class type. It should not be public.
return new L128X256Mix(this);
}
+
+ /** {@inheritDoc} */
+ @Override
+ public SplittableUniformRandomProvider split(UniformRandomProvider source) {
+ return create(source.nextLong(), source);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Stream<SplittableUniformRandomProvider> splits(long streamSize, SplittableUniformRandomProvider source) {
+ return RandomStreams.generateWithSeed(streamSize, source, L128X256Mix::create);
+ }
+
+ /**
+ * Create a new instance using the given {@code seed} and {@code source} of randomness
+ * to initialise the instance.
+ *
+ * @param seed Seed used to initialise the instance.
+ * @param source Source of randomness used to initialise the instance.
+ * @return A new instance.
+ */
+ private static SplittableUniformRandomProvider create(long seed, UniformRandomProvider source) {
+ // LCG state. The addition lower-half uses the input seed.
+ // The LCG addition parameter is set to odd so left-shift the seed.
+ final long s0 = source.nextLong();
+ final long s1 = seed << 1;
+ final long s2 = source.nextLong();
+ final long s3 = source.nextLong();
+ // XBG state must not be all zero
+ long x0 = source.nextLong();
+ long x1 = source.nextLong();
+ long x2 = source.nextLong();
+ long x3 = source.nextLong();
+ if ((x0 | x1 | x2 | x3) == 0) {
+ // SplitMix style seed ensures at least one non-zero value
+ long z = s3;
+ x0 = LXMSupport.lea64(z);
+ x1 = LXMSupport.lea64(z += LXMSupport.GOLDEN_RATIO_64);
+ x2 = LXMSupport.lea64(z += LXMSupport.GOLDEN_RATIO_64);
+ x3 = LXMSupport.lea64(z + LXMSupport.GOLDEN_RATIO_64);
+ }
+ // The LCG addition parameter is set to odd so left-shift the seed
+ return new L128X256Mix(s0, s1, s2, s3, x0, x1, x2, x3);
+ }
}
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L64X1024Mix.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L64X1024Mix.java
index d78b0f80..5b4373bb 100644
--- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L64X1024Mix.java
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L64X1024Mix.java
@@ -17,9 +17,12 @@
package org.apache.commons.rng.core.source64;
+import java.util.stream.Stream;
import org.apache.commons.rng.JumpableUniformRandomProvider;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.core.util.NumberFactory;
+import org.apache.commons.rng.core.util.RandomStreams;
/**
* A 64-bit all purpose generator.
@@ -41,17 +44,27 @@ import org.apache.commons.rng.core.util.NumberFactory;
* against accidental correlation in a multi-threaded setting. The additive parameters must be
* different in the most significant 63-bits.
*
+ * <p>This generator implements
+ * {@link org.apache.commons.rng.SplittableUniformRandomProvider SplittableUniformRandomProvider}.
+ * The stream of generators created using the {@code splits} methods support parallelisation
+ * and are robust against accidental correlation by using unique values for the additive parameter
+ * for each instance in the same stream. The primitive streaming methods support parallelisation
+ * but with no assurances of accidental correlation; each thread uses a new instance with a
+ * randomly initialised state.
+ *
* @see <a href="https://doi.org/10.1145/3485525">Steele & Vigna (2021) Proc. ACM Programming
* Languages 5, 1-31</a>
* @see <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/random/package-summary.html">
* JDK 17 java.util.random javadoc</a>
* @since 1.5
*/
-public class L64X1024Mix extends AbstractL64 {
+public class L64X1024Mix extends AbstractL64 implements SplittableUniformRandomProvider {
/** Size of the seed vector. */
private static final int SEED_SIZE = 18;
- /** Size of the state vector. */
+ /** Size of the XBG state vector. */
private static final int XBG_STATE_SIZE = 16;
+ /** Size of the LCG state vector. */
+ private static final int LCG_STATE_SIZE = SEED_SIZE - XBG_STATE_SIZE;
/** LCG multiplier. */
private static final long M = LXMSupport.M64;
@@ -176,4 +189,47 @@ public class L64X1024Mix extends AbstractL64 {
// the correct class type. It should not be public.
return new L64X1024Mix(this);
}
+
+ /** {@inheritDoc} */
+ @Override
+ public SplittableUniformRandomProvider split(UniformRandomProvider source) {
+ return create(source.nextLong(), source);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Stream<SplittableUniformRandomProvider> splits(long streamSize, SplittableUniformRandomProvider source) {
+ return RandomStreams.generateWithSeed(streamSize, source, L64X1024Mix::create);
+ }
+
+ /**
+ * Create a new instance using the given {@code seed} and {@code source} of randomness
+ * to initialise the instance.
+ *
+ * @param seed Seed used to initialise the instance.
+ * @param source Source of randomness used to initialise the instance.
+ * @return A new instance.
+ */
+ private static SplittableUniformRandomProvider create(long seed, UniformRandomProvider source) {
+ final long[] s = new long[SEED_SIZE];
+ // LCG state. The addition uses the input seed.
+ // The LCG addition parameter is set to odd so left-shift the seed.
+ s[0] = seed << 1;
+ s[1] = source.nextLong();
+ // XBG state must not be all zero
+ long x = 0;
+ for (int i = LCG_STATE_SIZE; i < s.length; i++) {
+ s[i] = source.nextLong();
+ x |= s[i];
+ }
+ if (x == 0) {
+ // SplitMix style seed ensures at least one non-zero value
+ x = s[LCG_STATE_SIZE - 1];
+ for (int i = LCG_STATE_SIZE; i < s.length; i++) {
+ s[i] = LXMSupport.lea64(x);
+ x += LXMSupport.GOLDEN_RATIO_64;
+ }
+ }
+ return new L64X1024Mix(s);
+ }
}
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L64X128Mix.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L64X128Mix.java
index 0555f1fd..2ca27d23 100644
--- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L64X128Mix.java
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L64X128Mix.java
@@ -17,6 +17,11 @@
package org.apache.commons.rng.core.source64;
+import java.util.stream.Stream;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
+import org.apache.commons.rng.UniformRandomProvider;
+import org.apache.commons.rng.core.util.RandomStreams;
+
/**
* A 64-bit all purpose generator.
*
@@ -37,13 +42,21 @@ package org.apache.commons.rng.core.source64;
* against accidental correlation in a multi-threaded setting. The additive parameters must be
* different in the most significant 63-bits.
*
+ * <p>This generator implements
+ * {@link org.apache.commons.rng.SplittableUniformRandomProvider SplittableUniformRandomProvider}.
+ * The stream of generators created using the {@code splits} methods support parallelisation
+ * and are robust against accidental correlation by using unique values for the additive parameter
+ * for each instance in the same stream. The primitive streaming methods support parallelisation
+ * but with no assurances of accidental correlation; each thread uses a new instance with a
+ * randomly initialised state.
+ *
* @see <a href="https://doi.org/10.1145/3485525">Steele & Vigna (2021) Proc. ACM Programming
* Languages 5, 1-31</a>
* @see <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/random/package-summary.html">
* JDK 17 java.util.random javadoc</a>
* @since 1.5
*/
-public class L64X128Mix extends AbstractL64X128 {
+public class L64X128Mix extends AbstractL64X128 implements SplittableUniformRandomProvider {
/**
* Creates a new instance.
*
@@ -123,4 +136,40 @@ public class L64X128Mix extends AbstractL64X128 {
// the correct class type. It should not be public.
return new L64X128Mix(this);
}
+
+ /** {@inheritDoc} */
+ @Override
+ public SplittableUniformRandomProvider split(UniformRandomProvider source) {
+ return create(source.nextLong(), source);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Stream<SplittableUniformRandomProvider> splits(long streamSize, SplittableUniformRandomProvider source) {
+ return RandomStreams.generateWithSeed(streamSize, source, L64X128Mix::create);
+ }
+
+ /**
+ * Create a new instance using the given {@code seed} and {@code source} of randomness
+ * to initialise the instance.
+ *
+ * @param seed Seed used to initialise the instance.
+ * @param source Source of randomness used to initialise the instance.
+ * @return A new instance.
+ */
+ private static SplittableUniformRandomProvider create(long seed, UniformRandomProvider source) {
+ // LCG state. The addition uses the input seed.
+ // The LCG addition parameter is set to odd so left-shift the seed.
+ final long s0 = seed << 1;
+ final long s1 = source.nextLong();
+ // XBG state must not be all zero
+ long x0 = source.nextLong();
+ long x1 = source.nextLong();
+ if ((x0 | x1) == 0) {
+ // SplitMix style seed ensures at least one non-zero value
+ x0 = LXMSupport.lea64(s1);
+ x1 = LXMSupport.lea64(s1 + LXMSupport.GOLDEN_RATIO_64);
+ }
+ return new L64X128Mix(s0, s1, x0, x1);
+ }
}
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L64X128StarStar.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L64X128StarStar.java
index e949ff7b..dc56fa2d 100644
--- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L64X128StarStar.java
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L64X128StarStar.java
@@ -17,6 +17,11 @@
package org.apache.commons.rng.core.source64;
+import java.util.stream.Stream;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
+import org.apache.commons.rng.UniformRandomProvider;
+import org.apache.commons.rng.core.util.RandomStreams;
+
/**
* A 64-bit all purpose generator.
*
@@ -43,7 +48,7 @@ package org.apache.commons.rng.core.source64;
* JDK 17 java.util.random javadoc</a>
* @since 1.5
*/
-public class L64X128StarStar extends AbstractL64X128 {
+public class L64X128StarStar extends AbstractL64X128 implements SplittableUniformRandomProvider {
/**
* Creates a new instance.
*
@@ -123,4 +128,40 @@ public class L64X128StarStar extends AbstractL64X128 {
// the correct class type. It should not be public.
return new L64X128StarStar(this);
}
+
+ /** {@inheritDoc} */
+ @Override
+ public SplittableUniformRandomProvider split(UniformRandomProvider source) {
+ return create(source.nextLong(), source);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Stream<SplittableUniformRandomProvider> splits(long streamSize, SplittableUniformRandomProvider source) {
+ return RandomStreams.generateWithSeed(streamSize, source, L64X128StarStar::create);
+ }
+
+ /**
+ * Create a new instance using the given {@code seed} and {@code source} of randomness
+ * to initialise the instance.
+ *
+ * @param seed Seed used to initialise the instance.
+ * @param source Source of randomness used to initialise the instance.
+ * @return A new instance.
+ */
+ private static SplittableUniformRandomProvider create(long seed, UniformRandomProvider source) {
+ // LCG state. The addition uses the input seed.
+ // The LCG addition parameter is set to odd so left-shift the seed.
+ final long s0 = seed << 1;
+ final long s1 = source.nextLong();
+ // XBG state must not be all zero
+ long x0 = source.nextLong();
+ long x1 = source.nextLong();
+ if ((x0 | x1) == 0) {
+ // SplitMix style seed ensures at least one non-zero value
+ x0 = LXMSupport.lea64(s1);
+ x1 = LXMSupport.lea64(s1 + LXMSupport.GOLDEN_RATIO_64);
+ }
+ return new L64X128StarStar(s0, s1, x0, x1);
+ }
}
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L64X256Mix.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L64X256Mix.java
index 61ad84d2..9cc36443 100644
--- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L64X256Mix.java
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/L64X256Mix.java
@@ -17,9 +17,12 @@
package org.apache.commons.rng.core.source64;
+import java.util.stream.Stream;
import org.apache.commons.rng.JumpableUniformRandomProvider;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.core.util.NumberFactory;
+import org.apache.commons.rng.core.util.RandomStreams;
/**
* A 64-bit all purpose generator.
@@ -41,13 +44,21 @@ import org.apache.commons.rng.core.util.NumberFactory;
* against accidental correlation in a multi-threaded setting. The additive parameters must be
* different in the most significant 63-bits.
*
+ * <p>This generator implements
+ * {@link org.apache.commons.rng.SplittableUniformRandomProvider SplittableUniformRandomProvider}.
+ * The stream of generators created using the {@code splits} methods support parallelisation
+ * and are robust against accidental correlation by using unique values for the additive parameter
+ * for each instance in the same stream. The primitive streaming methods support parallelisation
+ * but with no assurances of accidental correlation; each thread uses a new instance with a
+ * randomly initialised state.
+ *
* @see <a href="https://doi.org/10.1145/3485525">Steele & Vigna (2021) Proc. ACM Programming
* Languages 5, 1-31</a>
* @see <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/random/package-summary.html">
* JDK 17 java.util.random javadoc</a>
* @since 1.5
*/
-public class L64X256Mix extends AbstractL64 {
+public class L64X256Mix extends AbstractL64 implements SplittableUniformRandomProvider {
/** Size of the seed vector. */
private static final int SEED_SIZE = 6;
/** Size of the XBG state vector. */
@@ -219,4 +230,45 @@ public class L64X256Mix extends AbstractL64 {
// the correct class type. It should not be public.
return new L64X256Mix(this);
}
+
+ /** {@inheritDoc} */
+ @Override
+ public SplittableUniformRandomProvider split(UniformRandomProvider source) {
+ return create(source.nextLong(), source);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Stream<SplittableUniformRandomProvider> splits(long streamSize, SplittableUniformRandomProvider source) {
+ return RandomStreams.generateWithSeed(streamSize, source, L64X256Mix::create);
+ }
+
+ /**
+ * Create a new instance using the given {@code seed} and {@code source} of randomness
+ * to initialise the instance.
+ *
+ * @param seed Seed used to initialise the instance.
+ * @param source Source of randomness used to initialise the instance.
+ * @return A new instance.
+ */
+ private static SplittableUniformRandomProvider create(long seed, UniformRandomProvider source) {
+ // LCG state. The addition uses the input seed.
+ // The LCG addition parameter is set to odd so left-shift the seed.
+ final long s0 = seed << 1;
+ final long s1 = source.nextLong();
+ // XBG state must not be all zero
+ long x0 = source.nextLong();
+ long x1 = source.nextLong();
+ long x2 = source.nextLong();
+ long x3 = source.nextLong();
+ if ((x0 | x1 | x2 | x3) == 0) {
+ // SplitMix style seed ensures at least one non-zero value
+ long z = s1;
+ x0 = LXMSupport.lea64(z);
+ x1 = LXMSupport.lea64(z += LXMSupport.GOLDEN_RATIO_64);
+ x2 = LXMSupport.lea64(z += LXMSupport.GOLDEN_RATIO_64);
+ x3 = LXMSupport.lea64(z + LXMSupport.GOLDEN_RATIO_64);
+ }
+ return new L64X256Mix(s0, s1, x0, x1, x2, x3);
+ }
}
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/LXMSupport.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/LXMSupport.java
index 540df88d..3e897c86 100644
--- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/LXMSupport.java
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/LXMSupport.java
@@ -68,6 +68,14 @@ final class LXMSupport {
* </pre>
*/
static final long C128PH = 0x61139b28883277c3L;
+ /**
+ * The fractional part of the golden ratio, phi, scaled to 64-bits and rounded to odd.
+ * <pre>
+ * phi = (sqrt(5) - 1) / 2) * 2^64
+ * </pre>
+ * @see <a href="https://en.wikipedia.org/wiki/Golden_ratio">Golden ratio</a>
+ */
+ static final long GOLDEN_RATIO_64 = 0x9e3779b97f4a7c15L;
/** A mask to convert an {@code int} to an unsigned integer stored as a {@code long}. */
private static final long INT_TO_UNSIGNED_BYTE_MASK = 0xffff_ffffL;
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/util/RandomStreams.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/util/RandomStreams.java
new file mode 100644
index 00000000..e6db6fa7
--- /dev/null
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/util/RandomStreams.java
@@ -0,0 +1,278 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.rng.core.util;
+
+import java.util.Objects;
+import java.util.Spliterator;
+import java.util.function.Consumer;
+import java.util.stream.Stream;
+import java.util.stream.StreamSupport;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
+import org.apache.commons.rng.UniformRandomProvider;
+
+/**
+ * Utility for creating streams using a source of randomness.
+ */
+public final class RandomStreams {
+ /** The number of bits of each random character in the seed.
+ * The generation algorithm will work if this is in the range [2, 30]. */
+ private static final int SEED_CHAR_BITS = 4;
+
+ /**
+ * A factory for creating objects using a seed and a using a source of randomness.
+ *
+ * @param <T> the object type
+ */
+ public interface ObjectFactory<T> {
+ /**
+ * Creates the object.
+ *
+ * @param seed Seed used to initialise the instance.
+ * @param source Source of randomness used to initialise the instance.
+ * @return the object
+ */
+ T create(long seed, UniformRandomProvider source);
+ }
+
+ /**
+ * Class contains only static methods.
+ */
+ private RandomStreams() {}
+
+ /**
+ * Returns a stream producing the given {@code streamSize} number of new objects
+ * generated using the supplied {@code source} of randomness using the {@code factory}.
+ *
+ * <p>A {@code long} seed is provided for each object instance using the stream position
+ * and random bits created from the supplied {@code source}.
+ *
+ * <p>The stream supports parallel execution by splitting the provided {@code source}
+ * of randomness. Consequently objects in the same position in the stream created from
+ * a sequential stream may be created from a different source of randomness than a parallel
+ * stream; it is not expected that parallel execution will create the same final
+ * collection of objects.
+ *
+ * @param <T> the object type
+ * @param streamSize Number of objects to generate.
+ * @param source A source of randomness used to initialise the new instances; this may
+ * be split to provide a source of randomness across a parallel stream.
+ * @param factory Factory to create new instances.
+ * @return a stream of objects; the stream is limited to the given {@code streamSize}.
+ * @throws IllegalArgumentException if {@code streamSize} is negative.
+ * @throws NullPointerException if {@code source} or {@code factory} is null
+ */
+ public static <T> Stream<T> generateWithSeed(long streamSize,
+ SplittableUniformRandomProvider source,
+ ObjectFactory<T> factory) {
+ if (streamSize < 0) {
+ throw new IllegalArgumentException("Invalid stream size: " + streamSize);
+ }
+ Objects.requireNonNull(source, "source");
+ Objects.requireNonNull(factory, "factory");
+ final long seed = createSeed(source);
+ return StreamSupport
+ .stream(new SeededObjectSpliterator<>(0, streamSize, source, factory, seed), false);
+ }
+
+ /**
+ * Creates a seed to prepend to a counter. The seed is created to satisfy the following
+ * requirements:
+ * <ul>
+ * <li>The least significant bit is set
+ * <li>The seed is composed of characters from an n-bit alphabet
+ * <li>The character used in the least significant bits is unique
+ * <li>The other characters are sampled uniformly from the remaining (n-1) characters
+ * </ul>
+ *
+ * <p>The composed seed is created using {@code ((seed << shift) | count)}
+ * where the shift is applied to ensure non-overlap of the shifted seed and
+ * the count. This is achieved by ensuring the lowest 1-bit of the seed is
+ * above the highest 1-bit of the count. The shift is a multiple of n to ensure
+ * the character used in the least significant bits aligns with higher characters
+ * after a shift. As higher characters exclude the least significant character
+ * no shifted seed can duplicate previously observed composed seeds. This holds
+ * until the least significant character itself is shifted out of the composed seed.
+ *
+ * <p>The seed generation algorithm starts with a random series of bits with the lowest bit
+ * set. Any occurrences of the least significant character in the remaining characters are
+ * replaced using {@link UniformRandomProvider#nextInt()}.
+ *
+ * <p>The remaining characters will be rejected at a rate of 2<sup>-n</sup>. The
+ * character size is a compromise between a low rejection rate and the highest supported
+ * count that may receive a prepended seed.
+ *
+ * <p>The JDK's {@code java.util.random} package uses 4-bits for the character size when
+ * creating a stream of SplittableGenerator. This achieves a rejection rate
+ * of {@code 1/16}. Using this size will require 1 call to generate a {@code long} and
+ * on average 1 call to {@code nextInt(15)}. The maximum supported stream size with a unique
+ * seed per object is 2<sup>60</sup>. The algorithm here also uses a character size of 4-bits;
+ * this simplifies the implementation as there are exactly 16 characters. The algorithm is a
+ * different implementation to the JDK and creates an output seed with similar properties.
+ *
+ * @param rng Source of randomness.
+ * @return the seed
+ */
+ static long createSeed(UniformRandomProvider rng) {
+ // Initial random bits. Lowest bit must be set.
+ long bits = rng.nextLong() | 1;
+ // Mask to extract characters.
+ // Can be used to sample from (n-1) n-bit characters.
+ final long n = (1 << SEED_CHAR_BITS) - 1;
+
+ // Extract the unique character.
+ final long unique = bits & n;
+
+ // Check the rest of the characters do not match the unique character.
+ // This loop extracts the remaining characters and replaces if required.
+ // This will work if the characters do not evenly divide into 64 as we iterate
+ // over the count of remaining bits. The original order is maintained so that
+ // if the bits already satisfy the requirements they are unchanged.
+ for (int i = SEED_CHAR_BITS; i < Long.SIZE; i += SEED_CHAR_BITS) {
+ // Next character
+ long c = (bits >>> i) & n;
+ if (c == unique) {
+ // Branch frequency of 2^-bits.
+ // This code is deliberately branchless.
+ // Avoid nextInt(n) using: c = floor(n * ([0, 2^32) / 2^32))
+ // Rejection rate for non-uniformity will be negligible: 2^32 % 15 == 1
+ // so any rejection algorithm only has to exclude 1 value from nextInt().
+ c = (n * Integer.toUnsignedLong(rng.nextInt())) >>> Integer.SIZE;
+ // Ensure the sample is uniform in [0, n] excluding the unique character
+ c = (unique + c + 1) & n;
+ // Replace by masking out the current character and bitwise add the new one
+ bits = (bits & ~(n << i)) | (c << i);
+ }
+ }
+ return bits;
+ }
+
+ /**
+ * Spliterator for streams of a given object type that can be created from a seed
+ * and source of randomness. The source of randomness is splittable allowing parallel
+ * stream support.
+ *
+ * <p>The seed is mixed with the stream position to ensure each object is created using
+ * a unique seed value. As the position increases the seed is left shifted until there
+ * is no bit overlap between the seed and the position, i.e the right-most 1-bit of the seed
+ * is larger than the left-most 1-bit of the position.
+ *s
+ * @param <T> the object type
+ */
+ private static final class SeededObjectSpliterator<T>
+ implements Spliterator<T> {
+ /** Message when the consumer action is null. */
+ private static final String NULL_ACTION = "action must not be null";
+
+ /** The current position in the range. */
+ private long position;
+ /** The upper limit of the range. */
+ private final long end;
+ /** Seed used to initialise the new instances. The least significant 1-bit of
+ * the seed must be above the most significant bit of the position. This is maintained
+ * by left shift when the position is updated. */
+ private long seed;
+ /** Source of randomness used to initialise the new instances. */
+ private final SplittableUniformRandomProvider source;
+ /** Factory to create new instances. */
+ private final ObjectFactory<T> factory;
+
+ /**
+ * @param start Start position of the stream (inclusive).
+ * @param end Upper limit of the stream (exclusive).
+ * @param source Source of randomness used to initialise the new instances.
+ * @param factory Factory to create new instances.
+ * @param seed Seed used to initialise the instances. The least significant 1-bit of
+ * the seed must be above the most significant bit of the {@code start} position.
+ */
+ SeededObjectSpliterator(long start, long end,
+ SplittableUniformRandomProvider source,
+ ObjectFactory<T> factory,
+ long seed) {
+ position = start;
+ this.end = end;
+ this.seed = seed;
+ this.source = source;
+ this.factory = factory;
+ }
+
+ @Override
+ public long estimateSize() {
+ return end - position;
+ }
+
+ @Override
+ public int characteristics() {
+ return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.IMMUTABLE;
+ }
+
+ @Override
+ public Spliterator<T> trySplit() {
+ final long start = position;
+ final long middle = (start + end) >>> 1;
+ if (middle <= start) {
+ return null;
+ }
+ // The child spliterator can use the same seed as the position does not overlap
+ final SeededObjectSpliterator<T> s =
+ new SeededObjectSpliterator<>(start, middle, source.split(), factory, seed);
+ // Since the position has increased ensure the seed does not overlap
+ position = middle;
+ while (seed != 0 && Long.compareUnsigned(Long.lowestOneBit(seed), middle) <= 0) {
+ seed <<= SEED_CHAR_BITS;
+ }
+ return s;
+ }
+
+ @Override
+ public boolean tryAdvance(Consumer<? super T> action) {
+ Objects.requireNonNull(action, NULL_ACTION);
+ final long pos = position;
+ if (pos < end) {
+ // Advance before exceptions from the action are relayed to the caller
+ position = pos + 1;
+ action.accept(factory.create(seed | pos, source));
+ // If the position overlaps the seed, shift it by 1 character
+ if ((position & seed) != 0) {
+ seed <<= SEED_CHAR_BITS;
+ }
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public void forEachRemaining(Consumer<? super T> action) {
+ Objects.requireNonNull(action, NULL_ACTION);
+ long pos = position;
+ final long last = end;
+ if (pos < last) {
+ // Ensure forEachRemaining is called only once
+ position = last;
+ final SplittableUniformRandomProvider s = source;
+ final ObjectFactory<T> f = factory;
+ do {
+ action.accept(f.create(seed | pos, s));
+ pos++;
+ // If the position overlaps the seed, shift it by 1 character
+ if ((pos & seed) != 0) {
+ seed <<= SEED_CHAR_BITS;
+ }
+ } while (pos < last);
+ }
+ }
+ }
+}
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/ProvidersList.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/ProvidersList.java
index 80eab849..0abf3a51 100644
--- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/ProvidersList.java
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/ProvidersList.java
@@ -74,6 +74,7 @@ import org.apache.commons.rng.core.source64.PcgRxsMXs64;
import org.apache.commons.rng.core.source64.DotyHumphreySmallFastCounting64;
import org.apache.commons.rng.JumpableUniformRandomProvider;
import org.apache.commons.rng.RestorableUniformRandomProvider;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
/**
* The purpose of this class is to provide the list of all generators
@@ -93,6 +94,8 @@ public final class ProvidersList {
private static final List<RestorableUniformRandomProvider> LIST64 = new ArrayList<>();
/** List of {@link JumpableUniformRandomProvider} RNGs. */
private static final List<JumpableUniformRandomProvider> LIST_JUMP = new ArrayList<>();
+ /** List of {@link SplittableUniformRandomProvider} RNGs. */
+ private static final List<SplittableUniformRandomProvider> LIST_SPLIT = new ArrayList<>();
static {
// External generator for creating a random seed.
@@ -166,10 +169,13 @@ public final class ProvidersList {
// Complete list.
LIST.addAll(LIST32);
LIST.addAll(LIST64);
- // Dynamically identify the Jumpable RNGs
+ // Dynamically identify the sub-type RNGs
LIST.stream()
.filter(rng -> rng instanceof JumpableUniformRandomProvider)
.forEach(rng -> LIST_JUMP.add((JumpableUniformRandomProvider) rng));
+ LIST.stream()
+ .filter(rng -> rng instanceof SplittableUniformRandomProvider)
+ .forEach(rng -> LIST_SPLIT.add((SplittableUniformRandomProvider) rng));
} catch (Exception e) {
// CHECKSTYLE: stop Regexp
System.err.println("Unexpected exception while creating the list of generators: " + e);
@@ -223,4 +229,14 @@ public final class ProvidersList {
public static Iterable<JumpableUniformRandomProvider> listJumpable() {
return Collections.unmodifiableList(LIST_JUMP);
}
+
+ /**
+ * Subclasses that are "parametric" tests can forward the call to
+ * the "@Parameters"-annotated method to this method.
+ *
+ * @return the list of {@link SplittableUniformRandomProvider} generators.
+ */
+ public static Iterable<SplittableUniformRandomProvider> listSplittable() {
+ return Collections.unmodifiableList(LIST_SPLIT);
+ }
}
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/RandomAssert.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/RandomAssert.java
index 85462a1e..75cf2f10 100644
--- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/RandomAssert.java
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/RandomAssert.java
@@ -243,6 +243,40 @@ public final class RandomAssert {
}
}
+ /**
+ * Assert that the two random generators produce a different output for
+ * {@link UniformRandomProvider#nextInt()} over the given number of cycles.
+ *
+ * @param cycles Number of cycles.
+ * @param rng1 Random generator 1.
+ * @param rng2 Random generator 2.
+ */
+ public static void assertNextIntNotEquals(int cycles, UniformRandomProvider rng1, UniformRandomProvider rng2) {
+ for (int i = 0; i < cycles; i++) {
+ if (rng1.nextInt() != rng2.nextInt()) {
+ return;
+ }
+ }
+ Assertions.fail(() -> cycles + " cycles of nextb has same output");
+ }
+
+ /**
+ * Assert that the two random generators produce a different output for
+ * {@link UniformRandomProvider#nextLong()} over the given number of cycles.
+ *
+ * @param cycles Number of cycles.
+ * @param rng1 Random generator 1.
+ * @param rng2 Random generator 2.
+ */
+ public static void assertNextLongNotEquals(int cycles, UniformRandomProvider rng1, UniformRandomProvider rng2) {
+ for (int i = 0; i < cycles; i++) {
+ if (rng1.nextLong() != rng2.nextLong()) {
+ return;
+ }
+ }
+ Assertions.fail(() -> cycles + " cycles of nextLong has same output");
+ }
+
/**
* Assert that the random generator produces zero output for
* {@link UniformRandomProvider#nextInt()} over the given number of cycles.
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/SplittableProvidersParametricTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/SplittableProvidersParametricTest.java
new file mode 100644
index 00000000..bf2721e9
--- /dev/null
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/SplittableProvidersParametricTest.java
@@ -0,0 +1,359 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.rng.core;
+
+import java.util.HashSet;
+import java.util.Set;
+import java.util.Spliterator;
+import java.util.SplittableRandom;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.function.Consumer;
+import java.util.function.UnaryOperator;
+import java.util.stream.Stream;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
+import org.apache.commons.rng.UniformRandomProvider;
+import org.apache.commons.rng.core.util.RandomStreamsTestHelper;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.MethodSource;
+
+/**
+ * Tests which all {@link SplittableUniformRandomProvider} generators must pass.
+ */
+class SplittableProvidersParametricTest {
+ /** The expected characteristics for the spliterator from the splittable stream. */
+ private static final int SPLITERATOR_CHARACTERISTICS =
+ Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.IMMUTABLE;
+
+ /**
+ * Dummy class for checking the behavior of the SplittableUniformRandomProvider.
+ * All generation and split methods throw an exception. This can be used to test
+ * exception conditions for arguments to default stream functions.
+ */
+ private static class DummyGenerator implements SplittableUniformRandomProvider {
+ /** An instance. */
+ static final DummyGenerator INSTANCE = new DummyGenerator();
+
+ @Override
+ public long nextLong() {
+ throw new UnsupportedOperationException("The nextLong method should not be invoked");
+ }
+
+ @Override
+ public SplittableUniformRandomProvider split(UniformRandomProvider source) {
+ throw new UnsupportedOperationException("The split(source) method should not be invoked");
+ }
+ }
+
+ /**
+ * Thread-safe class for checking the behavior of the SplittableUniformRandomProvider.
+ * Generation methods default to ThreadLocalRandom. Split methods return the same instance.
+ * This is a functioning generator that can be used as a source to seed splitting.
+ */
+ private static class ThreadLocalGenerator implements SplittableUniformRandomProvider {
+ /** An instance. */
+ static final ThreadLocalGenerator INSTANCE = new ThreadLocalGenerator();
+
+ @Override
+ public long nextLong() {
+ return ThreadLocalRandom.current().nextLong();
+ }
+
+ @Override
+ public SplittableUniformRandomProvider split(UniformRandomProvider source) {
+ return this;
+ }
+ }
+
+ /**
+ * Gets the list of splittable generators.
+ *
+ * @return the list
+ */
+ private static Iterable<SplittableUniformRandomProvider> getSplittableProviders() {
+ return ProvidersList.listSplittable();
+ }
+
+ /**
+ * Test that the split methods throw when the source of randomness is null.
+ */
+ @ParameterizedTest
+ @MethodSource("getSplittableProviders")
+ void testSplitThrowsWithNullSource(SplittableUniformRandomProvider generator) {
+ Assertions.assertThrows(NullPointerException.class, () -> generator.split(null));
+ }
+
+ /**
+ * Test that the random generator returned from the split is a new instance of the same class.
+ */
+ @ParameterizedTest
+ @MethodSource("getSplittableProviders")
+ void testSplitReturnsANewInstance(SplittableUniformRandomProvider generator) {
+ assertSplitReturnsANewInstance(SplittableUniformRandomProvider::split, generator);
+ }
+
+ /**
+ * Test that the random generator returned from the split(source) is a new instance of the same class.
+ */
+ @ParameterizedTest
+ @MethodSource("getSplittableProviders")
+ void testSplitWithSourceReturnsANewInstance(SplittableUniformRandomProvider generator) {
+ assertSplitReturnsANewInstance(s -> s.split(ThreadLocalGenerator.INSTANCE), generator);
+ }
+
+ /**
+ * Assert that the random generator returned from the split function is a new instance of the same class.
+ *
+ * @param splitFunction Split function to test.
+ * @param generator RNG under test.
+ */
+ private static void assertSplitReturnsANewInstance(UnaryOperator<SplittableUniformRandomProvider> splitFunction,
+ SplittableUniformRandomProvider generator) {
+ final UniformRandomProvider child = splitFunction.apply(generator);
+ Assertions.assertNotSame(generator, child, "The child instance should be a different object");
+ Assertions.assertEquals(generator.getClass(), child.getClass(), "The child instance should be the same class");
+ RandomAssert.assertNextLongNotEquals(10, generator, child);
+ }
+
+ /**
+ * Test that the split method is reproducible when used with the same generator source in the
+ * same state.
+ */
+ @ParameterizedTest
+ @MethodSource("getSplittableProviders")
+ void testSplitWithSourceIsReproducible(SplittableUniformRandomProvider generator) {
+ final long seed = ThreadLocalRandom.current().nextLong();
+ UniformRandomProvider rng1 = generator.split(new SplittableRandom(seed)::nextLong);
+ UniformRandomProvider rng2 = generator.split(new SplittableRandom(seed)::nextLong);
+ RandomAssert.assertNextLongEquals(10, rng1, rng2);
+ }
+
+ /**
+ * Test that the other stream splits methods all call the
+ * {@link SplittableUniformRandomProvider#splits(long, SplittableUniformRandomProvider)} method.
+ * This is tested by checking the spliterator is the same.
+ *
+ * <p>This test serves to ensure the default implementations in SplittableUniformRandomProvider
+ * eventually call the same method. The RNG implementation thus only has to override one method.
+ */
+ @ParameterizedTest
+ @MethodSource("getSplittableProviders")
+ void testSplitsMethodsUseSameSpliterator(SplittableUniformRandomProvider generator) {
+ final long size = 10;
+ final Spliterator<SplittableUniformRandomProvider> s = generator.splits(size, generator).spliterator();
+ Assertions.assertEquals(s.getClass(), generator.splits().spliterator().getClass());
+ Assertions.assertEquals(s.getClass(), generator.splits(size).spliterator().getClass());
+ Assertions.assertEquals(s.getClass(), generator.splits(ThreadLocalGenerator.INSTANCE).spliterator().getClass());
+ }
+
+ @ParameterizedTest
+ @MethodSource("getSplittableProviders")
+ void testSplitsSize(SplittableUniformRandomProvider generator) {
+ for (final long size : new long[] {0, 1, 7, 13}) {
+ Assertions.assertEquals(size, generator.splits(size).count(), "splits");
+ Assertions.assertEquals(size, generator.splits(size, ThreadLocalGenerator.INSTANCE).count(), "splits with source");
+ }
+ }
+
+ @ParameterizedTest
+ @MethodSource("getSplittableProviders")
+ void testSplits(SplittableUniformRandomProvider generator) {
+ assertSplits(generator, false);
+ }
+
+ @ParameterizedTest
+ @MethodSource("getSplittableProviders")
+ void testSplitsParallel(SplittableUniformRandomProvider generator) {
+ assertSplits(generator, true);
+ }
+
+ /**
+ * Test the splits method returns a stream of unique instances. The test uses a
+ * fixed source of randomness such that the only randomness is from the stream
+ * position.
+ *
+ * @param generator Generator
+ * @param parallel true to use a parallel stream
+ */
+ private static void assertSplits(SplittableUniformRandomProvider generator, boolean parallel) {
+ final long size = 13;
+ for (final long seed : new long[] {0, RandomStreamsTestHelper.createSeed(ThreadLocalGenerator.INSTANCE)}) {
+ final SplittableUniformRandomProvider source = new SplittableUniformRandomProvider() {
+ @Override
+ public long nextLong() {
+ return seed;
+ }
+
+ @Override
+ public SplittableUniformRandomProvider split(UniformRandomProvider source) {
+ return this;
+ }
+ };
+ // Test the assumption that the seed will be passed through (lowest bit is set)
+ Assertions.assertEquals(seed | 1, RandomStreamsTestHelper.createSeed(source));
+
+ Stream<SplittableUniformRandomProvider> stream = generator.splits(size, source);
+ Assertions.assertFalse(stream.isParallel(), "Initial stream should be sequential");
+ if (parallel) {
+ stream = stream.parallel();
+ Assertions.assertTrue(stream.isParallel(), "Stream should be parallel");
+ }
+
+ // Check the instance is a new object of the same type.
+ // These will be hashed using the system identity hash code.
+ final Set<SplittableUniformRandomProvider> observed = ConcurrentHashMap.newKeySet();
+ observed.add(generator);
+ stream.forEach(r -> {
+ Assertions.assertTrue(observed.add(r), "Instance should be unique");
+ Assertions.assertEquals(generator.getClass(), r.getClass());
+ });
+ // Note: observed contains the original generator so subtract 1
+ Assertions.assertEquals(size, observed.size() - 1);
+
+ // Test instances generate different values.
+ // The only randomness is from the stream position.
+ final long[] values = observed.stream().mapToLong(r -> {
+ // Warm up generator with some cycles.
+ // E.g. LXM generators return the first value from the initial state.
+ for (int i = 0; i < 10; i++) {
+ r.nextLong();
+ }
+ return r.nextLong();
+ }).distinct().toArray();
+ // This test is looking for different values.
+ // To avoid the rare case of not all distinct we relax the threshold to
+ // half the generators. This will spot errors where all generators are
+ // the same.
+ Assertions.assertTrue(values.length > size / 2,
+ () -> "splits did not seed randomness from the stream position. Initial seed = " + seed);
+ }
+ }
+
+ // Test adapted from stream tests in commons-rng-client-api module
+
+ /**
+ * Helper method to raise an assertion error inside an action passed to a Spliterator
+ * when the action should not be invoked.
+ *
+ * @see Spliterator#tryAdvance(Consumer)
+ * @see Spliterator#forEachRemaining(Consumer)
+ */
+ private static void failSpliteratorShouldBeEmpty() {
+ Assertions.fail("Spliterator should not have any remaining elements");
+ }
+
+ @ParameterizedTest
+ @MethodSource("getSplittableProviders")
+ void testSplitsInvalidStreamSizeThrows(SplittableUniformRandomProvider rng) {
+ Assertions.assertThrows(IllegalArgumentException.class, () -> rng.splits(-1), "splits(size)");
+ final SplittableUniformRandomProvider source = DummyGenerator.INSTANCE;
+ Assertions.assertThrows(IllegalArgumentException.class, () -> rng.splits(-1, source), "splits(size, source)");
+ }
+
+ @ParameterizedTest
+ @MethodSource("getSplittableProviders")
+ void testSplitsUnlimitedStreamSize(SplittableUniformRandomProvider rng) {
+ assertUnlimitedSpliterator(rng.splits().spliterator(), "splits()");
+ final SplittableUniformRandomProvider source = ThreadLocalGenerator.INSTANCE;
+ assertUnlimitedSpliterator(rng.splits(source).spliterator(), "splits(source)");
+ }
+
+ /**
+ * Assert the spliterator has an unlimited expected size and the characteristics for a sized
+ * immutable stream.
+ *
+ * @param spliterator Spliterator.
+ * @param msg Error message.
+ */
+ private static void assertUnlimitedSpliterator(Spliterator<?> spliterator, String msg) {
+ Assertions.assertEquals(Long.MAX_VALUE, spliterator.estimateSize(), msg);
+ Assertions.assertTrue(spliterator.hasCharacteristics(SPLITERATOR_CHARACTERISTICS),
+ () -> String.format("%s: characteristics = %s, expected %s", msg,
+ Integer.toBinaryString(spliterator.characteristics()),
+ Integer.toBinaryString(SPLITERATOR_CHARACTERISTICS)
+ ));
+ }
+
+ @ParameterizedTest
+ @MethodSource("getSplittableProviders")
+ void testSplitsNullSourceThrows(SplittableUniformRandomProvider rng) {
+ final SplittableUniformRandomProvider source = null;
+ Assertions.assertThrows(NullPointerException.class, () -> rng.splits(source));
+ Assertions.assertThrows(NullPointerException.class, () -> rng.splits(1, source));
+ }
+
+ @ParameterizedTest
+ @MethodSource("getSplittableProviders")
+ void testSplitsSpliterator(SplittableUniformRandomProvider rng) {
+ // Split a large spliterator into four smaller ones;
+ // each is used to test different functionality
+ final long size = 41;
+ Spliterator<SplittableUniformRandomProvider> s1 = rng.splits(size).spliterator();
+ Assertions.assertEquals(size, s1.estimateSize());
+ final Spliterator<SplittableUniformRandomProvider> s2 = s1.trySplit();
+ final Spliterator<SplittableUniformRandomProvider> s3 = s1.trySplit();
+ final Spliterator<SplittableUniformRandomProvider> s4 = s2.trySplit();
+ Assertions.assertEquals(size, s1.estimateSize() + s2.estimateSize() + s3.estimateSize() + s4.estimateSize());
+
+ // s1. Test cannot split indefinitely
+ while (s1.estimateSize() > 1) {
+ final long currentSize = s1.estimateSize();
+ final Spliterator<SplittableUniformRandomProvider> other = s1.trySplit();
+ Assertions.assertEquals(currentSize, s1.estimateSize() + other.estimateSize());
+ s1 = other;
+ }
+ Assertions.assertNull(s1.trySplit(), "Cannot split when size <= 1");
+
+ // Check the instance is a new object of the same type.
+ // These will be hashed using the system identity hash code.
+ final HashSet<SplittableUniformRandomProvider> observed = new HashSet<>();
+ observed.add(rng);
+
+ final Consumer<SplittableUniformRandomProvider> action = r -> {
+ Assertions.assertTrue(observed.add(r), "Instance should be unique");
+ Assertions.assertEquals(rng.getClass(), r.getClass());
+ };
+
+ // s2. Test advance
+ for (long newSize = s2.estimateSize(); newSize-- > 0;) {
+ Assertions.assertTrue(s2.tryAdvance(action));
+ Assertions.assertEquals(newSize, s2.estimateSize(), "s2 size estimate");
+ }
+ Assertions.assertFalse(s2.tryAdvance(r -> failSpliteratorShouldBeEmpty()));
+ s2.forEachRemaining(r -> failSpliteratorShouldBeEmpty());
+
+ // s3. Test forEachRemaining
+ s3.forEachRemaining(action);
+ Assertions.assertEquals(0, s3.estimateSize());
+ s3.forEachRemaining(r -> failSpliteratorShouldBeEmpty());
+
+ // s4. Test tryAdvance and forEachRemaining when the action throws an exception
+ final IllegalStateException ex = new IllegalStateException();
+ final Consumer<SplittableUniformRandomProvider> badAction = r -> {
+ throw ex;
+ };
+ final long currentSize = s4.estimateSize();
+ Assertions.assertTrue(currentSize > 1, "Spliterator requires more elements to test advance");
+ Assertions.assertSame(ex, Assertions.assertThrows(IllegalStateException.class, () -> s4.tryAdvance(badAction)));
+ Assertions.assertEquals(currentSize - 1, s4.estimateSize(), "Spliterator should be advanced even when action throws");
+
+ Assertions.assertSame(ex, Assertions.assertThrows(IllegalStateException.class, () -> s4.forEachRemaining(badAction)));
+ Assertions.assertEquals(0, s4.estimateSize(), "Spliterator should be finished even when action throws");
+ s4.forEachRemaining(r -> failSpliteratorShouldBeEmpty());
+ }
+}
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/L32X64MixTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/L32X64MixTest.java
index a448ca93..b947b52c 100644
--- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/L32X64MixTest.java
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/L32X64MixTest.java
@@ -18,7 +18,10 @@ package org.apache.commons.rng.core.source32;
import java.util.stream.Stream;
import org.apache.commons.rng.LongJumpableUniformRandomProvider;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
+import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.core.RandomAssert;
+import org.junit.jupiter.api.Test;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;
@@ -135,4 +138,29 @@ class L32X64MixTest extends AbstractLXMTest {
final L32X64Mix rng2 = new L32X64Mix(seed[0], seed[1], seed[2], seed[3]);
RandomAssert.assertNextLongEquals(seed.length * 2, rng1, rng2);
}
+
+ /**
+ * Test split with zero bits from the source. This should be robust to escape the state
+ * of all zero bits that will create an invalid state for the xor-based generator (XBG).
+ */
+ @Test
+ void testSplitWithZeroBits() {
+ final UniformRandomProvider zeroSource = () -> 0;
+ final int[] seed = new int[Factory.INSTANCE.seedSize()];
+ // Here we copy the split which sets the LCG increment to odd
+ seed[(Factory.INSTANCE.lcgSeedSize() / 2) - 1] = 1;
+ final SplittableUniformRandomProvider rng1 = new L32X64Mix(seed);
+ final SplittableUniformRandomProvider rng2 = rng1.split(zeroSource);
+ RandomAssert.assertNextIntNotEquals(seed.length * 2, rng1, rng2);
+
+ // Since we know how the zero seed is amended
+ int z = 0;
+ for (int i = Factory.INSTANCE.lcgSeedSize(); i < seed.length; i++) {
+ seed[i] = LXMSupport.lea32(z);
+ z += LXMSupport.GOLDEN_RATIO_32;
+ }
+ final SplittableUniformRandomProvider rng3 = new L32X64Mix(seed);
+ final SplittableUniformRandomProvider rng4 = rng1.split(zeroSource);
+ RandomAssert.assertNextIntEquals(seed.length * 2, rng3, rng4);
+ }
}
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L128X1024MixTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L128X1024MixTest.java
index 171782bb..276bf54d 100644
--- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L128X1024MixTest.java
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L128X1024MixTest.java
@@ -19,6 +19,10 @@ package org.apache.commons.rng.core.source64;
import java.util.Arrays;
import java.util.stream.Stream;
import org.apache.commons.rng.LongJumpableUniformRandomProvider;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
+import org.apache.commons.rng.UniformRandomProvider;
+import org.apache.commons.rng.core.RandomAssert;
+import org.junit.jupiter.api.Test;
import org.junit.jupiter.params.provider.Arguments;
/**
@@ -137,4 +141,29 @@ class L128X1024MixTest extends AbstractLXMTest {
0x479d66e6c85c98beL, 0xba9516550452d729L, 0x299e54b50cebe420L, 0x8fde3ca654cd399dL,
}));
}
+
+ /**
+ * Test split with zero bits from the source. This should be robust to escape the state
+ * of all zero bits that will create an invalid state for the xor-based generator (XBG).
+ */
+ @Test
+ void testSplitWithZeroBits() {
+ final UniformRandomProvider zeroSource = () -> 0;
+ final long[] seed = new long[Factory.INSTANCE.seedSize()];
+ // Here we copy the split which sets the LCG increment to odd
+ seed[(Factory.INSTANCE.lcgSeedSize() / 2) - 1] = 1;
+ final SplittableUniformRandomProvider rng1 = new L128X1024Mix(seed);
+ final SplittableUniformRandomProvider rng2 = rng1.split(zeroSource);
+ RandomAssert.assertNextLongNotEquals(seed.length * 2, rng1, rng2);
+
+ // Since we know how the zero seed is amended
+ long z = 0;
+ for (int i = Factory.INSTANCE.lcgSeedSize(); i < seed.length; i++) {
+ seed[i] = LXMSupport.lea64(z);
+ z += LXMSupport.GOLDEN_RATIO_64;
+ }
+ final SplittableUniformRandomProvider rng3 = new L128X1024Mix(seed);
+ final SplittableUniformRandomProvider rng4 = rng1.split(zeroSource);
+ RandomAssert.assertNextLongEquals(seed.length * 2, rng3, rng4);
+ }
}
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L128X128MixTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L128X128MixTest.java
index 102fc15a..24bad789 100644
--- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L128X128MixTest.java
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L128X128MixTest.java
@@ -18,7 +18,10 @@ package org.apache.commons.rng.core.source64;
import java.util.stream.Stream;
import org.apache.commons.rng.LongJumpableUniformRandomProvider;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
+import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.core.RandomAssert;
+import org.junit.jupiter.api.Test;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;
@@ -138,4 +141,29 @@ class L128X128MixTest extends AbstractLXMTest {
final L128X128Mix rng2 = new L128X128Mix(seed[0], seed[1], seed[2], seed[3], seed[4], seed[5]);
RandomAssert.assertNextLongEquals(seed.length * 2, rng1, rng2);
}
+
+ /**
+ * Test split with zero bits from the source. This should be robust to escape the state
+ * of all zero bits that will create an invalid state for the xor-based generator (XBG).
+ */
+ @Test
+ void testSplitWithZeroBits() {
+ final UniformRandomProvider zeroSource = () -> 0;
+ final long[] seed = new long[Factory.INSTANCE.seedSize()];
+ // Here we copy the split which sets the LCG increment to odd
+ seed[(Factory.INSTANCE.lcgSeedSize() / 2) - 1] = 1;
+ final SplittableUniformRandomProvider rng1 = new L128X128Mix(seed);
+ final SplittableUniformRandomProvider rng2 = rng1.split(zeroSource);
+ RandomAssert.assertNextLongNotEquals(seed.length * 2, rng1, rng2);
+
+ // Since we know how the zero seed is amended
+ long z = 0;
+ for (int i = Factory.INSTANCE.lcgSeedSize(); i < seed.length; i++) {
+ seed[i] = LXMSupport.lea64(z);
+ z += LXMSupport.GOLDEN_RATIO_64;
+ }
+ final SplittableUniformRandomProvider rng3 = new L128X128Mix(seed);
+ final SplittableUniformRandomProvider rng4 = rng1.split(zeroSource);
+ RandomAssert.assertNextLongEquals(seed.length * 2, rng3, rng4);
+ }
}
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L128X256MixTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L128X256MixTest.java
index cfdf95d3..9317874a 100644
--- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L128X256MixTest.java
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L128X256MixTest.java
@@ -18,7 +18,10 @@ package org.apache.commons.rng.core.source64;
import java.util.stream.Stream;
import org.apache.commons.rng.LongJumpableUniformRandomProvider;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
+import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.core.RandomAssert;
+import org.junit.jupiter.api.Test;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;
@@ -138,4 +141,29 @@ class L128X256MixTest extends AbstractLXMTest {
seed[4], seed[5], seed[6], seed[7]);
RandomAssert.assertNextLongEquals(seed.length * 2, rng1, rng2);
}
+
+ /**
+ * Test split with zero bits from the source. This should be robust to escape the state
+ * of all zero bits that will create an invalid state for the xor-based generator (XBG).
+ */
+ @Test
+ void testSplitWithZeroBits() {
+ final UniformRandomProvider zeroSource = () -> 0;
+ final long[] seed = new long[Factory.INSTANCE.seedSize()];
+ // Here we copy the split which sets the LCG increment to odd
+ seed[(Factory.INSTANCE.lcgSeedSize() / 2) - 1] = 1;
+ final SplittableUniformRandomProvider rng1 = new L128X256Mix(seed);
+ final SplittableUniformRandomProvider rng2 = rng1.split(zeroSource);
+ RandomAssert.assertNextLongNotEquals(seed.length * 2, rng1, rng2);
+
+ // Since we know how the zero seed is amended
+ long z = 0;
+ for (int i = Factory.INSTANCE.lcgSeedSize(); i < seed.length; i++) {
+ seed[i] = LXMSupport.lea64(z);
+ z += LXMSupport.GOLDEN_RATIO_64;
+ }
+ final SplittableUniformRandomProvider rng3 = new L128X256Mix(seed);
+ final SplittableUniformRandomProvider rng4 = rng1.split(zeroSource);
+ RandomAssert.assertNextLongEquals(seed.length * 2, rng3, rng4);
+ }
}
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L64X1024MixTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L64X1024MixTest.java
index 871ce7aa..cc53a161 100644
--- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L64X1024MixTest.java
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L64X1024MixTest.java
@@ -19,6 +19,10 @@ package org.apache.commons.rng.core.source64;
import java.util.Arrays;
import java.util.stream.Stream;
import org.apache.commons.rng.LongJumpableUniformRandomProvider;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
+import org.apache.commons.rng.UniformRandomProvider;
+import org.apache.commons.rng.core.RandomAssert;
+import org.junit.jupiter.api.Test;
import org.junit.jupiter.params.provider.Arguments;
/**
@@ -137,4 +141,29 @@ class L64X1024MixTest extends AbstractLXMTest {
0xaa84a5cf5b0668caL, 0xecb643d0e758e7edL, 0xe6eba4065ff373abL, 0xb80a1412a869cef7L,
}));
}
+
+ /**
+ * Test split with zero bits from the source. This should be robust to escape the state
+ * of all zero bits that will create an invalid state for the xor-based generator (XBG).
+ */
+ @Test
+ void testSplitWithZeroBits() {
+ final UniformRandomProvider zeroSource = () -> 0;
+ final long[] seed = new long[Factory.INSTANCE.seedSize()];
+ // Here we copy the split which sets the LCG increment to odd
+ seed[(Factory.INSTANCE.lcgSeedSize() / 2) - 1] = 1;
+ final SplittableUniformRandomProvider rng1 = new L64X1024Mix(seed);
+ final SplittableUniformRandomProvider rng2 = rng1.split(zeroSource);
+ RandomAssert.assertNextLongNotEquals(seed.length * 2, rng1, rng2);
+
+ // Since we know how the zero seed is amended
+ long z = 0;
+ for (int i = Factory.INSTANCE.lcgSeedSize(); i < seed.length; i++) {
+ seed[i] = LXMSupport.lea64(z);
+ z += LXMSupport.GOLDEN_RATIO_64;
+ }
+ final SplittableUniformRandomProvider rng3 = new L64X1024Mix(seed);
+ final SplittableUniformRandomProvider rng4 = rng1.split(zeroSource);
+ RandomAssert.assertNextLongEquals(seed.length * 2, rng3, rng4);
+ }
}
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L64X128MixTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L64X128MixTest.java
index cafc9539..289ec973 100644
--- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L64X128MixTest.java
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L64X128MixTest.java
@@ -18,7 +18,10 @@ package org.apache.commons.rng.core.source64;
import java.util.stream.Stream;
import org.apache.commons.rng.LongJumpableUniformRandomProvider;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
+import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.core.RandomAssert;
+import org.junit.jupiter.api.Test;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;
@@ -135,4 +138,29 @@ class L64X128MixTest extends AbstractLXMTest {
final L64X128Mix rng2 = new L64X128Mix(seed[0], seed[1], seed[2], seed[3]);
RandomAssert.assertNextLongEquals(seed.length * 2, rng1, rng2);
}
+
+ /**
+ * Test split with zero bits from the source. This should be robust to escape the state
+ * of all zero bits that will create an invalid state for the xor-based generator (XBG).
+ */
+ @Test
+ void testSplitWithZeroBits() {
+ final UniformRandomProvider zeroSource = () -> 0;
+ final long[] seed = new long[Factory.INSTANCE.seedSize()];
+ // Here we copy the split which sets the LCG increment to odd
+ seed[(Factory.INSTANCE.lcgSeedSize() / 2) - 1] = 1;
+ final SplittableUniformRandomProvider rng1 = new L64X128Mix(seed);
+ final SplittableUniformRandomProvider rng2 = rng1.split(zeroSource);
+ RandomAssert.assertNextLongNotEquals(seed.length * 2, rng1, rng2);
+
+ // Since we know how the zero seed is amended
+ long z = 0;
+ for (int i = Factory.INSTANCE.lcgSeedSize(); i < seed.length; i++) {
+ seed[i] = LXMSupport.lea64(z);
+ z += LXMSupport.GOLDEN_RATIO_64;
+ }
+ final SplittableUniformRandomProvider rng3 = new L64X128Mix(seed);
+ final SplittableUniformRandomProvider rng4 = rng1.split(zeroSource);
+ RandomAssert.assertNextLongEquals(seed.length * 2, rng3, rng4);
+ }
}
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L64X128StarStarTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L64X128StarStarTest.java
index ed8275e5..aad16ff0 100644
--- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L64X128StarStarTest.java
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L64X128StarStarTest.java
@@ -18,7 +18,10 @@ package org.apache.commons.rng.core.source64;
import java.util.stream.Stream;
import org.apache.commons.rng.LongJumpableUniformRandomProvider;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
+import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.core.RandomAssert;
+import org.junit.jupiter.api.Test;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;
@@ -141,4 +144,29 @@ class L64X128StarStarTest extends AbstractLXMTest {
final L64X128StarStar rng2 = new L64X128StarStar(seed[0], seed[1], seed[2], seed[3]);
RandomAssert.assertNextLongEquals(seed.length * 2, rng1, rng2);
}
+
+ /**
+ * Test split with zero bits from the source. This should be robust to escape the state
+ * of all zero bits that will create an invalid state for the xor-based generator (XBG).
+ */
+ @Test
+ void testSplitWithZeroBits() {
+ final UniformRandomProvider zeroSource = () -> 0;
+ final long[] seed = new long[Factory.INSTANCE.seedSize()];
+ // Here we copy the split which sets the LCG increment to odd
+ seed[(Factory.INSTANCE.lcgSeedSize() / 2) - 1] = 1;
+ final SplittableUniformRandomProvider rng1 = new L64X128StarStar(seed);
+ final SplittableUniformRandomProvider rng2 = rng1.split(zeroSource);
+ RandomAssert.assertNextLongNotEquals(seed.length * 2, rng1, rng2);
+
+ // Since we know how the zero seed is amended
+ long z = 0;
+ for (int i = Factory.INSTANCE.lcgSeedSize(); i < seed.length; i++) {
+ seed[i] = LXMSupport.lea64(z);
+ z += LXMSupport.GOLDEN_RATIO_64;
+ }
+ final SplittableUniformRandomProvider rng3 = new L64X128StarStar(seed);
+ final SplittableUniformRandomProvider rng4 = rng1.split(zeroSource);
+ RandomAssert.assertNextLongEquals(seed.length * 2, rng3, rng4);
+ }
}
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L64X256MixTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L64X256MixTest.java
index a0c46591..1792a10d 100644
--- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L64X256MixTest.java
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/L64X256MixTest.java
@@ -18,7 +18,10 @@ package org.apache.commons.rng.core.source64;
import java.util.stream.Stream;
import org.apache.commons.rng.LongJumpableUniformRandomProvider;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
+import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.core.RandomAssert;
+import org.junit.jupiter.api.Test;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;
@@ -138,4 +141,29 @@ class L64X256MixTest extends AbstractLXMTest {
final L64X256Mix rng2 = new L64X256Mix(seed[0], seed[1], seed[2], seed[3], seed[4], seed[5]);
RandomAssert.assertNextLongEquals(seed.length * 2, rng1, rng2);
}
+
+ /**
+ * Test split with zero bits from the source. This should be robust to escape the state
+ * of all zero bits that will create an invalid state for the xor-based generator (XBG).
+ */
+ @Test
+ void testSplitWithZeroBits() {
+ final UniformRandomProvider zeroSource = () -> 0;
+ final long[] seed = new long[Factory.INSTANCE.seedSize()];
+ // Here we copy the split which sets the LCG increment to odd
+ seed[(Factory.INSTANCE.lcgSeedSize() / 2) - 1] = 1;
+ final SplittableUniformRandomProvider rng1 = new L64X256Mix(seed);
+ final SplittableUniformRandomProvider rng2 = rng1.split(zeroSource);
+ RandomAssert.assertNextLongNotEquals(seed.length * 2, rng1, rng2);
+
+ // Since we know how the zero seed is amended
+ long z = 0;
+ for (int i = Factory.INSTANCE.lcgSeedSize(); i < seed.length; i++) {
+ seed[i] = LXMSupport.lea64(z);
+ z += LXMSupport.GOLDEN_RATIO_64;
+ }
+ final SplittableUniformRandomProvider rng3 = new L64X256Mix(seed);
+ final SplittableUniformRandomProvider rng4 = rng1.split(zeroSource);
+ RandomAssert.assertNextLongEquals(seed.length * 2, rng3, rng4);
+ }
}
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/util/RandomStreamsTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/util/RandomStreamsTest.java
new file mode 100644
index 00000000..87b0fbca
--- /dev/null
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/util/RandomStreamsTest.java
@@ -0,0 +1,448 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.rng.core.util;
+
+import java.util.Arrays;
+import java.util.Spliterator;
+import java.util.SplittableRandom;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ForkJoinPool;
+import java.util.concurrent.atomic.AtomicLong;
+import java.util.function.Consumer;
+import java.util.function.IntConsumer;
+import java.util.function.LongConsumer;
+import java.util.function.Supplier;
+import java.util.stream.LongStream;
+import org.apache.commons.math3.stat.inference.ChiSquareTest;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
+import org.apache.commons.rng.UniformRandomProvider;
+import org.apache.commons.rng.core.util.RandomStreams.ObjectFactory;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+import org.junit.jupiter.params.provider.ValueSource;
+
+/**
+ * Tests for {@link RandomStreams}.
+ */
+class RandomStreamsTest {
+ /** The size in bits of the seed characters. */
+ private static final int CHAR_BITS = 4;
+
+ /**
+ * Class for outputting a unique sequence from the nextLong() method even under
+ * recursive splitting. Splitting creates a new instance.
+ */
+ private static class SequenceGenerator implements SplittableUniformRandomProvider {
+ /** The value for nextLong. */
+ private final AtomicLong value;
+
+ /**
+ * @param seed Sequence seed value.
+ */
+ SequenceGenerator(long seed) {
+ value = new AtomicLong(seed);
+ }
+
+ /**
+ * @param value The value for nextLong.
+ */
+ SequenceGenerator(AtomicLong value) {
+ this.value = value;
+ }
+
+ @Override
+ public long nextLong() {
+ return value.getAndIncrement();
+ }
+
+ @Override
+ public SplittableUniformRandomProvider split(UniformRandomProvider source) {
+ // Ignore the source (use of the source is optional)
+ return new SequenceGenerator(value);
+ }
+ }
+
+ /**
+ * Class for decoding the combined seed ((seed << shift) | position).
+ * Requires the unshifted seed. The shift is assumed to be a multiple of 4.
+ * The first call to the consumer will extract the current position.
+ * Further calls will compare the value with the predicted value using
+ * the last known position.
+ */
+ private static class SeedDecoder implements Consumer<Long>, LongConsumer {
+ /** The initial (unshifted) seed. */
+ private final long initial;
+ /** The current shifted seed. */
+ private long seed;
+ /** The last known position. */
+ private long position = -1;
+
+ /**
+ * @param initial Unshifted seed value.
+ */
+ SeedDecoder(long initial) {
+ this.initial = initial;
+ }
+
+ @Override
+ public void accept(long value) {
+ if (position < 0) {
+ // Search for the initial seed value
+ seed = initial;
+ long mask = -1;
+ while (seed != 0 && (value & mask) != seed) {
+ seed <<= CHAR_BITS;
+ mask <<= CHAR_BITS;
+ }
+ if (seed == 0) {
+ Assertions.fail(() -> String.format("Failed to decode position from %s using seed %s",
+ Long.toBinaryString(value), Long.toBinaryString(initial)));
+ }
+ // Remove the seed contribution leaving the position
+ position = value & ~seed;
+ } else {
+ // Predict
+ final long expected = position + 1;
+ //seed = initial;
+ while (seed != 0 && Long.compareUnsigned(Long.lowestOneBit(seed), expected) <= 0) {
+ seed <<= CHAR_BITS;
+ }
+ Assertions.assertEquals(expected | seed, value);
+ position = expected;
+ }
+ }
+
+ @Override
+ public void accept(Long t) {
+ accept(t.longValue());
+ }
+
+ /**
+ * Reset the decoder.
+ */
+ void reset() {
+ position = -1;
+ }
+ }
+
+ /**
+ * Test the seed has the required properties:
+ * <ul>
+ * <li>Test the seed has an odd character in the least significant position
+ * <li>Test the remaining characters in the seed do not match this character
+ * <li>Test the distribution of characters is uniform
+ * <ul>
+ *
+ * <p>The test assumes the character size is 4-bits.
+ *
+ * @param seed the seed
+ */
+ @ParameterizedTest
+ @ValueSource(longs = {1628346812812L})
+ void testCreateSeed(long seed) {
+ final UniformRandomProvider rng = new SplittableRandom(seed)::nextLong;
+
+ // Histogram the distribution for each unique 4-bit character
+ final int m = (1 << CHAR_BITS) - 1;
+ // Number of remaining characters
+ final int n = (int) Math.ceil((Long.SIZE - CHAR_BITS) / CHAR_BITS);
+ final int[][] h = new int[m + 1][m + 1];
+ final int samples = 1 << 16;
+ for (int i = 0; i < samples; i++) {
+ long s = RandomStreams.createSeed(rng);
+ final int unique = (int) (s & m);
+ for (int j = 0; j < n; j++) {
+ s >>>= CHAR_BITS;
+ h[unique][(int) (s & m)]++;
+ }
+ }
+
+ // Test unique characters are always odd.
+ final int[] empty = new int[m + 1];
+ for (int i = 0; i <= m; i += 2) {
+ Assertions.assertArrayEquals(empty, h[i], "Even histograms should be empty");
+ }
+
+ // Test unique characters are not repeated
+ for (int i = 1; i <= m; i += 2) {
+ Assertions.assertEquals(0, h[i][i]);
+ }
+
+ // Chi-square test the distribution of unique characters
+ final long[] sum = new long[(m + 1) / 2];
+ for (int i = 1; i <= m; i += 2) {
+ final long total = Arrays.stream(h[i]).sum();
+ Assertions.assertEquals(0, total % n, "Samples should be a multiple of the number of characters");
+ sum[i / 2] = total / n;
+ }
+
+ assertChiSquare(sum, () -> "Unique character distribution");
+
+ // Chi-square test the distribution for each unique character.
+ // Note: This will fail if the characters do not evenly divide into 64.
+ // In that case the expected values are not uniform as the final
+ // character will be truncated and skew the expected values to lower characters.
+ // For simplicity this has not been accounted for as 4-bits evenly divides 64.
+ Assertions.assertEquals(0, Long.SIZE % CHAR_BITS, "Character distribution cannot be tested as uniform");
+ for (int i = 1; i <= m; i += 2) {
+ final long[] obs = Arrays.stream(h[i]).filter(c -> c != 0).asLongStream().toArray();
+ final int c = i;
+ assertChiSquare(obs, () -> "Other character distribution for unique character " + c);
+ }
+ }
+
+ /**
+ * Assert the observations are uniform using a chi-square test.
+ *
+ * @param obs Observations.
+ * @param msg Failure message prefix.
+ */
+ private static void assertChiSquare(long[] obs, Supplier<String> msg) {
+ final ChiSquareTest t = new ChiSquareTest();
+ final double alpha = 0.001;
+ final double[] expected = new double[obs.length];
+ Arrays.fill(expected, 1.0 / obs.length);
+ final double p = t.chiSquareTest(expected, obs);
+ Assertions.assertFalse(p < alpha, () -> String.format("%s: chi2 p-value: %s < %s", msg.get(), p, alpha));
+ }
+
+ @ParameterizedTest
+ @ValueSource(longs = {-1, -2, Long.MIN_VALUE})
+ void testGenerateWithSeedInvalidStreamSizeThrows(long size) {
+ final SplittableUniformRandomProvider source = new SequenceGenerator(0);
+ final ObjectFactory<Long> factory = (s, r) -> Long.valueOf(s);
+ final IllegalArgumentException ex1 = Assertions.assertThrows(IllegalArgumentException.class,
+ () -> RandomStreams.generateWithSeed(size, source, factory));
+ // Check the exception method is consistent with UniformRandomProvider stream methods
+ final IllegalArgumentException ex2 = Assertions.assertThrows(IllegalArgumentException.class,
+ () -> source.ints(size));
+ Assertions.assertEquals(ex2.getMessage(), ex1.getMessage(), "Inconsistent exception message");
+ }
+
+ @Test
+ void testGenerateWithSeedNullArgumentThrows() {
+ final long size = 10;
+ final SplittableUniformRandomProvider source = new SequenceGenerator(0);
+ final ObjectFactory<Long> factory = (s, r) -> Long.valueOf(s);
+ Assertions.assertThrows(NullPointerException.class,
+ () -> RandomStreams.generateWithSeed(size, null, factory));
+ Assertions.assertThrows(NullPointerException.class,
+ () -> RandomStreams.generateWithSeed(size, source, null));
+ }
+
+ /**
+ * Test that the seed passed to the factory is ((seed << shift) | position).
+ * This is done by creating an initial seed value of 1. When removed the
+ * remaining values should be a sequence.
+ *
+ * @param threads Number of threads.
+ * @param streamSize Stream size.
+ */
+ @ParameterizedTest
+ @CsvSource({
+ "1, 23",
+ "4, 31",
+ "4, 3",
+ "8, 127",
+ })
+ void testGenerateWithSeed(int threads, long streamSize) throws InterruptedException, ExecutionException {
+ // Provide a generator that results in the seed being set as 1.
+ final SplittableUniformRandomProvider rng = new SplittableUniformRandomProvider() {
+ @Override
+ public long nextLong() {
+ return 1;
+ }
+
+ @Override
+ public SplittableUniformRandomProvider split(UniformRandomProvider source) {
+ return this;
+ }
+ };
+ Assertions.assertEquals(1, RandomStreams.createSeed(rng), "Unexpected seed value");
+
+ // Create a factory that will return the seed passed to the factory
+ final ObjectFactory<Long> factory = (s, r) -> {
+ Assertions.assertSame(rng, r, "The source RNG is not used");
+ return Long.valueOf(s);
+ };
+
+ // Stream in a custom pool
+ final ForkJoinPool threadPool = new ForkJoinPool(threads);
+ Long[] values;
+ try {
+ values = threadPool.submit(() ->
+ RandomStreams.generateWithSeed(streamSize, rng, factory).parallel().toArray(Long[]::new)).get();
+ } finally {
+ threadPool.shutdown();
+ }
+
+ // Remove the highest 1 bit from each long. The rest should be a sequence.
+ final long[] actual = Arrays.stream(values).mapToLong(Long::longValue)
+ .map(l -> l - Long.highestOneBit(l)).sorted().toArray();
+ final long[] expected = LongStream.range(0, streamSize).toArray();
+ Assertions.assertArrayEquals(expected, actual);
+ }
+
+ @Test
+ void testGenerateWithSeedSpliteratorThrows() {
+ final long size = 10;
+ final SplittableUniformRandomProvider source = new SequenceGenerator(0);
+ final ObjectFactory<Long> factory = (s, r) -> Long.valueOf(s);
+ final Spliterator<Long> s = RandomStreams.generateWithSeed(size, source, factory).spliterator();
+ final Consumer<Long> badAction = null;
+ final NullPointerException ex1 = Assertions.assertThrows(NullPointerException.class, () -> s.tryAdvance(badAction), "tryAdvance");
+ final NullPointerException ex2 = Assertions.assertThrows(NullPointerException.class, () -> s.forEachRemaining(badAction), "forEachRemaining");
+ // Check the exception method is consistent with UniformRandomProvider stream methods
+ final NullPointerException ex3 = Assertions.assertThrows(NullPointerException.class, () -> source.ints().spliterator().tryAdvance((IntConsumer) null), "tryAdvance");
+ Assertions.assertEquals(ex3.getMessage(), ex1.getMessage(), "Inconsistent tryAdvance exception message");
+ Assertions.assertEquals(ex3.getMessage(), ex2.getMessage(), "Inconsistent forEachRemaining exception message");
+ }
+
+ @Test
+ void testGenerateWithSeedSpliterator() {
+ // Create an initial seed value. This should not be modified by the algorithm
+ // when generating a 'new' seed from the RNG.
+ final long initial = RandomStreams.createSeed(new SplittableRandom()::nextLong);
+ final SplittableUniformRandomProvider rng = new SplittableUniformRandomProvider() {
+ @Override
+ public long nextLong() {
+ return initial;
+ }
+
+ @Override
+ public SplittableUniformRandomProvider split(UniformRandomProvider source) {
+ return this;
+ }
+ };
+ Assertions.assertEquals(initial, RandomStreams.createSeed(rng), "Unexpected seed value");
+
+ // Create a factory that will return the seed passed to the factory
+ final ObjectFactory<Long> factory = (s, r) -> {
+ Assertions.assertSame(rng, r, "The source RNG is not used");
+ return Long.valueOf(s);
+ };
+
+ // Split a large spliterator into four smaller ones;
+ // each is used to test different functionality
+ final long size = 41;
+ Spliterator<Long> s1 = RandomStreams.generateWithSeed(size, rng, factory).spliterator();
+ Assertions.assertEquals(size, s1.estimateSize());
+ Assertions.assertTrue(s1.hasCharacteristics(Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.IMMUTABLE),
+ "Invalid characteristics");
+ final Spliterator<Long> s2 = s1.trySplit();
+ final Spliterator<Long> s3 = s1.trySplit();
+ final Spliterator<Long> s4 = s2.trySplit();
+ Assertions.assertEquals(size, s1.estimateSize() + s2.estimateSize() + s3.estimateSize() + s4.estimateSize());
+
+ // s1. Test cannot split indefinitely
+ while (s1.estimateSize() > 1) {
+ final long currentSize = s1.estimateSize();
+ final Spliterator<Long> other = s1.trySplit();
+ Assertions.assertEquals(currentSize, s1.estimateSize() + other.estimateSize());
+ s1 = other;
+ }
+ Assertions.assertNull(s1.trySplit(), "Cannot split when size <= 1");
+
+ // Create an action that will decode the shift and position using the
+ // known initial seed. This can be used to predict and assert the next value.
+ final SeedDecoder action = new SeedDecoder(initial);
+
+ // s2. Test advance
+ for (long newSize = s2.estimateSize(); newSize-- > 0;) {
+ Assertions.assertTrue(s2.tryAdvance(action));
+ Assertions.assertEquals(newSize, s2.estimateSize(), "s2 size estimate");
+ }
+ final Consumer<Long> throwIfCalled = r -> Assertions.fail("spliterator should be empty");
+ Assertions.assertFalse(s2.tryAdvance(throwIfCalled));
+ s2.forEachRemaining(throwIfCalled);
+
+ // s3. Test forEachRemaining
+ action.reset();
+ s3.forEachRemaining(action);
+ Assertions.assertEquals(0, s3.estimateSize());
+ s3.forEachRemaining(throwIfCalled);
+
+ // s4. Test tryAdvance and forEachRemaining when the action throws an exception
+ final IllegalStateException ex = new IllegalStateException();
+ final Consumer<Long> badAction = r -> {
+ throw ex;
+ };
+ final long currentSize = s4.estimateSize();
+ Assertions.assertTrue(currentSize > 1, "Spliterator requires more elements to test advance");
+ Assertions.assertSame(ex, Assertions.assertThrows(IllegalStateException.class, () -> s4.tryAdvance(badAction)));
+ Assertions.assertEquals(currentSize - 1, s4.estimateSize(), "Spliterator should be advanced even when action throws");
+
+ Assertions.assertSame(ex, Assertions.assertThrows(IllegalStateException.class, () -> s4.forEachRemaining(badAction)));
+ Assertions.assertEquals(0, s4.estimateSize(), "Spliterator should be finished even when action throws");
+ s4.forEachRemaining(throwIfCalled);
+ }
+
+ /**
+ * Test a very large stream size above 2<sup>60</sup>.
+ * In this case it is not possible to prepend a 4-bit character
+ * to the stream position. The seed passed to the factory will be the stream position.
+ */
+ @Test
+ void testLargeStreamSize() {
+ // Create an initial seed value. This should not be modified by the algorithm
+ // when generating a 'new' seed from the RNG.
+ final long initial = RandomStreams.createSeed(new SplittableRandom()::nextLong);
+ final SplittableUniformRandomProvider rng = new SplittableUniformRandomProvider() {
+ @Override
+ public long nextLong() {
+ return initial;
+ }
+
+ @Override
+ public SplittableUniformRandomProvider split(UniformRandomProvider source) {
+ return this;
+ }
+ };
+ Assertions.assertEquals(initial, RandomStreams.createSeed(rng), "Unexpected seed value");
+
+ // Create a factory that will return the seed passed to the factory
+ final ObjectFactory<Long> factory = (s, r) -> {
+ Assertions.assertSame(rng, r, "The source RNG is not used");
+ return Long.valueOf(s);
+ };
+
+ final Spliterator<Long> s = RandomStreams.generateWithSeed(1L << 62, rng, factory).spliterator();
+
+ // Split uses a divide-by-two approach. The child uses the smaller half.
+ final Spliterator<Long> s1 = s.trySplit();
+
+ // Lower half. The next position can be predicted using the decoder.
+ final SeedDecoder action = new SeedDecoder(initial);
+ long size = s1.estimateSize();
+ for (int i = 1; i <= 5; i++) {
+ Assertions.assertTrue(s1.tryAdvance(action));
+ Assertions.assertEquals(size - i, s1.estimateSize(), "s1 size estimate");
+ }
+
+ // Upper half. This should be just the stream position which we can
+ // collect with a call to advance.
+ final long[] expected = {0};
+ s.tryAdvance(seed -> expected[0] = seed);
+ size = s.estimateSize();
+ for (int i = 1; i <= 5; i++) {
+ Assertions.assertTrue(s.tryAdvance(seed -> Assertions.assertEquals(++expected[0], seed)));
+ Assertions.assertEquals(size - i, s.estimateSize(), "s size estimate");
+ }
+ }
+}
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/util/RandomStreamsTestHelper.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/util/RandomStreamsTestHelper.java
new file mode 100644
index 00000000..d1028e7b
--- /dev/null
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/util/RandomStreamsTestHelper.java
@@ -0,0 +1,39 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.rng.core.util;
+
+import org.apache.commons.rng.UniformRandomProvider;
+
+/**
+ * Test helper class to expose package-private functionality for tests in other packages.
+ */
+public final class RandomStreamsTestHelper {
+
+ /** No instances. */
+ private RandomStreamsTestHelper() {}
+
+ /**
+ * Creates a seed to prepend to a counter. This method makes public the package-private
+ * seed generation method used in {@link RandomStreams} for test classes in other packages.
+ *
+ * @param rng Source of randomness.
+ * @return the seed
+ */
+ public static long createSeed(UniformRandomProvider rng) {
+ return RandomStreams.createSeed(rng);
+ }
+}
diff --git a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/RandomSource.java b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/RandomSource.java
index 2432631f..0c834499 100644
--- a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/RandomSource.java
+++ b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/RandomSource.java
@@ -783,6 +783,29 @@ public enum RandomSource {
return isAssignableTo(org.apache.commons.rng.LongJumpableUniformRandomProvider.class);
}
+ /**
+ * Checks whether the implementing class represented by this random source
+ * supports the {@link org.apache.commons.rng.SplittableUniformRandomProvider
+ * SplittableUniformRandomProvider} interface. If {@code true} the instance returned
+ * by {@link #create(RandomSource)} may be cast to the interface; otherwise a class
+ * cast exception will occur.
+ *
+ * <p>Usage example:</p>
+ * <pre><code>
+ * RandomSource source = ...;
+ * if (source.isSplittable()) {
+ * SplittableUniformRandomProvider rng =
+ * (SplittableUniformRandomProvider) source.create();
+ * }
+ * </code></pre>
+ *
+ * @return {@code true} if splittable
+ * @since 1.5
+ */
+ public boolean isSplittable() {
+ return isAssignableTo(org.apache.commons.rng.SplittableUniformRandomProvider.class);
+ }
+
/**
* Determines if the implementing class represented by this random source is either the same
* as, or is a subclass or subinterface of, the class or interface represented
diff --git a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/ProvidersCommonParametricTest.java b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/ProvidersCommonParametricTest.java
index da062de4..d32de81f 100644
--- a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/ProvidersCommonParametricTest.java
+++ b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/ProvidersCommonParametricTest.java
@@ -37,6 +37,7 @@ import org.apache.commons.rng.JumpableUniformRandomProvider;
import org.apache.commons.rng.LongJumpableUniformRandomProvider;
import org.apache.commons.rng.RandomProviderState;
import org.apache.commons.rng.RestorableUniformRandomProvider;
+import org.apache.commons.rng.SplittableUniformRandomProvider;
import org.apache.commons.rng.core.RandomProviderDefaultState;
import org.apache.commons.rng.core.source64.LongProvider;
import org.apache.commons.rng.core.source64.SplitMix64;
@@ -360,6 +361,9 @@ class ProvidersCommonParametricTest {
Assertions.assertEquals(rng instanceof LongJumpableUniformRandomProvider,
originalSource.isLongJumpable(),
"isLongJumpable");
+ Assertions.assertEquals(rng instanceof SplittableUniformRandomProvider,
+ originalSource.isSplittable(),
+ "isSplittable");
}
///// Support methods below.
diff --git a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/RandomSourceTest.java b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/RandomSourceTest.java
index 49bd9635..1fa09f59 100644
--- a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/RandomSourceTest.java
+++ b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/RandomSourceTest.java
@@ -92,6 +92,13 @@ class RandomSourceTest {
Assertions.assertTrue(RandomSource.XO_SHI_RO_256_SS.isLongJumpable(), "XO_SHI_RO_256_SS is LongJumpable");
}
+ @Test
+ void testIsSplittable() {
+ Assertions.assertFalse(RandomSource.JDK.isSplittable(), "JDK is not Splittable");
+ Assertions.assertTrue(RandomSource.L32_X64_MIX.isSplittable(), "L32_X64_MIX is Splittable");
+ Assertions.assertTrue(RandomSource.L64_X128_MIX.isSplittable(), "L64_X128_MIX is Splittable");
+ }
+
/**
* MSWS should not infinite loop if the input RNG fails to provide randomness to create a seed.
* See RNG-175.
diff --git a/src/main/resources/pmd/pmd-ruleset.xml b/src/main/resources/pmd/pmd-ruleset.xml
index 9c4e4daa..96e00ff1 100644
--- a/src/main/resources/pmd/pmd-ruleset.xml
+++ b/src/main/resources/pmd/pmd-ruleset.xml
@@ -121,7 +121,7 @@
or @SimpleName='ThreadLocalRandomSource' or @SimpleName='SeedFactory'
or @SimpleName='Coordinates' or @SimpleName='Hex' or @SimpleName='SpecialMath'
or @SimpleName='Conversions' or @SimpleName='MixFunctions' or @SimpleName='LXMSupport'
- or @SimpleName='UniformRandomProviderSupport']"/>
+ or @SimpleName='UniformRandomProviderSupport' or @SimpleName='RandomStreams']"/>
<!-- Allow samplers to have only factory constructors -->
<property name="utilityClassPattern" value="[A-Z][a-zA-Z0-9]+(Utils?|Helper|Sampler)" />
</properties>
@@ -279,4 +279,12 @@
</properties>
</rule>
+ <rule ref="category/java/performance.xml/AvoidArrayLoops">
+ <properties>
+ <!-- False positive. The array loop is generating, not copying, values. -->
+ <property name="violationSuppressXPath"
+ value="./ancestor-or-self::ClassOrInterfaceDeclaration[matches(@SimpleName, '^.*L.*X1024Mix$')]"/>
+ </properties>
+ </rule>
+
</ruleset>
diff --git a/src/main/resources/revapi/api-changes.json b/src/main/resources/revapi/api-changes.json
index f979bc87..608e1140 100644
--- a/src/main/resources/revapi/api-changes.json
+++ b/src/main/resources/revapi/api-changes.json
@@ -9,6 +9,12 @@
"code": "java.method.abstractMethodAdded",
"new": "method java.lang.Object org.apache.commons.rng.simple.internal.NativeSeedType::createSeed(int, int, int)",
"justification": "Abstract method added to enum; all implementations are within this class. This is an internal package with no compatibility enforcement."
+ },
+ {
+ "ignore": true,
+ "code": "java.class.externalClassExposedInAPI",
+ "new": "interface org.apache.commons.rng.SplittableUniformRandomProvider",
+ "justification": "Split support was added to the client API and can be used by other modules."
}
]
}