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 c7c4db8c9ad0de4a0aa33eaafc9254fd7134352b Author: Alex Herbert <[email protected]> AuthorDate: Fri Feb 13 16:00:42 2026 +0000 RNG-189: Add interface ArbitrarilyJumpableUniformRandomProvider --- .../ArbitrarilyJumpableUniformRandomProvider.java | 120 ++++++++++++++ .../commons/rng/UniformRandomProviderSupport.java | 18 +++ .../java/org/apache/commons/rng/package-info.java | 23 +++ ...bitrarilyJumpableUniformRandomProviderTest.java | 175 +++++++++++++++++++++ .../apache/commons/rng/simple/RandomSource.java | 27 +++- .../rng/simple/ProvidersCommonParametricTest.java | 4 + .../commons/rng/simple/RandomSourceTest.java | 7 + src/conf/checkstyle/checkstyle-suppressions.xml | 2 +- 8 files changed, 373 insertions(+), 3 deletions(-) diff --git a/commons-rng-client-api/src/main/java/org/apache/commons/rng/ArbitrarilyJumpableUniformRandomProvider.java b/commons-rng-client-api/src/main/java/org/apache/commons/rng/ArbitrarilyJumpableUniformRandomProvider.java new file mode 100644 index 00000000..2470a4ce --- /dev/null +++ b/commons-rng-client-api/src/main/java/org/apache/commons/rng/ArbitrarilyJumpableUniformRandomProvider.java @@ -0,0 +1,120 @@ +/* + * 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; + +import java.util.stream.Stream; + +/** + * Applies to generators that can be advanced an arbitrary number of steps of the output + * sequence in a single operation. + * + * <p>Implementations must ensure that a jump of a specified {@code distance} will advance + * the state cycle sufficiently that an equivalent number of sequential calls to the + * original provider will <strong>not overlap</strong> output from the advanced + * provider.</p> + * + * <p>For many applications, it suffices to jump forward by a power of two or some small + * multiple of a power of two, but this power of two may not be representable as a + * {@code long} value. To avoid the use of {@link java.math.BigInteger BigInteger} values + * as jump distances, double values are used instead.</p> + * + * <p>Typical usage in a multithreaded application is to create a single + * {@link ArbitrarilyJumpableUniformRandomProvider} and {@link #jump(double) jump} the + * generator forward while passing each copy generator to a worker thread. The jump + * {@code distance} should be sufficient to cover all expected output by each worker. + * Since each copy generator is also a {@link ArbitrarilyJumpableUniformRandomProvider} + * with care it is possible to further distribute generators within the original jump + * {@code distance} and use the entire state cycle in different ways.</p> + * + * @since 1.7 + */ +public interface ArbitrarilyJumpableUniformRandomProvider extends UniformRandomProvider { + /** + * Creates a copy of the {@link ArbitrarilyJumpableUniformRandomProvider} and then advances + * the state cycle of the current instance by the specified {@code distance}. + * The copy is returned. + * + * <p>The current state will be advanced in a single operation by the equivalent of a + * number of sequential calls to a method that updates the state cycle of the provider.</p> + * + * <p>Repeat invocations of this method will create a series of generators + * that are uniformly spaced at intervals of the output sequence. Each generator provides + * non-overlapping output for the length specified by {@code distance} for use in parallel + * computations.</p> + * + * @param distance Distance to jump forward with the state cycle. + * @return A copy of the current state. + * @throws IllegalArgumentException if {@code distance} is negative, + * or is greater than the period of this generator. + */ + ArbitrarilyJumpableUniformRandomProvider jump(double distance); + + /** + * Creates a copy of the {@link ArbitrarilyJumpableUniformRandomProvider} and then advances + * the state cycle of the current instance by a distance equal to 2<sup>{@code logDistance}</sup>. + * The copy is returned. + * + * <p>The current state will be advanced in a single operation by the equivalent of a + * number of sequential calls to a method that updates the state cycle of the provider.</p> + * + * <p>Repeat invocations of this method will create a series of generators + * that are uniformly spaced at intervals of the output sequence. Each generator provides + * non-overlapping output for the length specified by 2<sup>{@code logDistance}</sup> for use + * in parallel computations.</p> + * + * @param logDistance Base-2 logarithm of the distance to jump forward with the state cycle. + * @return A copy of the current state. + * @throws IllegalArgumentException if 2<sup>{@code logDistance}</sup> + * is greater than the period of this generator. + */ + ArbitrarilyJumpableUniformRandomProvider jumpPowerOfTwo(int logDistance); + + /** + * Returns an effectively unlimited stream of new random generators, each of which + * implements the {@link ArbitrarilyJumpableUniformRandomProvider} interface. The + * generators are output at integer multiples of the specified jump {@code distance} + * in the generator's state cycle. + * + * @param distance Distance to jump forward with the state cycle. + * @return a stream of random generators. + * @throws IllegalArgumentException if {@code distance} is negative, + * or is greater than the period of this generator. + */ + default Stream<ArbitrarilyJumpableUniformRandomProvider> jumps(double distance) { + UniformRandomProviderSupport.validateJumpDistance(distance); + return Stream.generate(() -> jump(distance)).sequential(); + } + + /** + * Returns a stream producing the given {@code streamSize} number of new random + * generators, each of which implements the {@link ArbitrarilyJumpableUniformRandomProvider} + * interface. The generators are output at integer multiples of the specified jump + * {@code distance} in the generator's state cycle. + * + * @param streamSize Number of objects to generate. + * @param distance Distance to jump forward with the state cycle. + * @return a stream of random generators; the stream is limited to the given + * {@code streamSize}. + * @throws IllegalArgumentException if {@code streamSize} is negative; + * or if {@code distance} is negative, or is greater than the period of this generator. + */ + default Stream<ArbitrarilyJumpableUniformRandomProvider> jumps(long streamSize, + double distance) { + UniformRandomProviderSupport.validateStreamSize(streamSize); + return jumps(distance).limit(streamSize); + } +} diff --git a/commons-rng-client-api/src/main/java/org/apache/commons/rng/UniformRandomProviderSupport.java b/commons-rng-client-api/src/main/java/org/apache/commons/rng/UniformRandomProviderSupport.java index e1a58102..7b9d9347 100644 --- a/commons-rng-client-api/src/main/java/org/apache/commons/rng/UniformRandomProviderSupport.java +++ b/commons-rng-client-api/src/main/java/org/apache/commons/rng/UniformRandomProviderSupport.java @@ -34,6 +34,8 @@ import java.util.function.ToLongFunction; final class UniformRandomProviderSupport { /** Message for an invalid stream size. */ private static final String INVALID_STREAM_SIZE = "Invalid stream size: "; + /** Message for an invalid jump distance. */ + private static final String INVALID_JUMP_DISTANCE = "Invalid jump distance: "; /** Message for an invalid upper bound (must be positive, finite and above zero). */ private static final String INVALID_UPPER_BOUND = "Upper bound must be above zero: "; /** Message format for an invalid range for lower inclusive and upper exclusive. */ @@ -58,6 +60,22 @@ final class UniformRandomProviderSupport { } } + /** + * Validate the jump distance. + * + * <p>Note it is not possible to validate if the jump distance is greater + * than the period of the generator as this is unknown. + * + * @param distance Jump distance. + * @throws IllegalArgumentException if {@code distance} is negative, or non-finite. + */ + static void validateJumpDistance(double distance) { + // Negation of logic will detect NaN + if (!(distance >= 0 && distance <= Double.MAX_VALUE)) { + throw new IllegalArgumentException(INVALID_JUMP_DISTANCE + distance); + } + } + /** * Validate the upper bound. * diff --git a/commons-rng-client-api/src/main/java/org/apache/commons/rng/package-info.java b/commons-rng-client-api/src/main/java/org/apache/commons/rng/package-info.java index 463621ff..9af771d9 100644 --- a/commons-rng-client-api/src/main/java/org/apache/commons/rng/package-info.java +++ b/commons-rng-client-api/src/main/java/org/apache/commons/rng/package-info.java @@ -19,6 +19,29 @@ * This package contains the library's interface to be used by client * code that needs a generator of sequences of pseudo-random numbers * that are <i>uniformly distributed</i> in a specified range. + * + * <p><strong>Jumpable Generators</strong> + * + * <p>Interfaces are specified for generators that are capable of advancing + * forward a large number of steps in the output period of the generator in a + * single jump. This can be used to create a series of non-overlapping generators + * for use in multithreaded applications. + * + * <p>Note that there is not a one-to-one relationship between the number of output random + * values from a provider and the number of steps from the underlying state cycle. This + * is due to: + * <ol> + * <li>Possible use of rejection algorithms to output a random value using multiple + * values from the state cycle.</li> + * <li>The number of bits required to generate a random value differing from the + * number of bits generated by the underlying source of randomness. For example + * generation of a 64-bit {@code long} value using a 32-bit source of randomness.</li> + * </ol> + * + * <p>Users are advised to use jumping generators with care to avoid + * overlapping output of multiple generators in parallel computations. + * A cautious approach is to use a jump distance far larger than the expected + * output length used by each generator. */ package org.apache.commons.rng; diff --git a/commons-rng-client-api/src/test/java/org/apache/commons/rng/ArbitrarilyJumpableUniformRandomProviderTest.java b/commons-rng-client-api/src/test/java/org/apache/commons/rng/ArbitrarilyJumpableUniformRandomProviderTest.java new file mode 100644 index 00000000..b8f8607f --- /dev/null +++ b/commons-rng-client-api/src/test/java/org/apache/commons/rng/ArbitrarilyJumpableUniformRandomProviderTest.java @@ -0,0 +1,175 @@ +/* + * 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; + +import java.util.HashSet; +import java.util.Set; +import java.util.stream.Stream; +import org.junit.jupiter.api.Assertions; +import org.junit.jupiter.params.ParameterizedTest; +import org.junit.jupiter.params.provider.Arguments; +import org.junit.jupiter.params.provider.MethodSource; +import org.junit.jupiter.params.provider.ValueSource; + +/** + * Tests for default method implementations in + * {@link ArbitrarilyJumpableUniformRandomProvider}. + * + * <p>Streams methods are asserted to call the corresponding jump method in the + * interface. + */ +class ArbitrarilyJumpableUniformRandomProviderTest { + /** + * Class for checking the behavior of the ArbitrarilyJumpableUniformRandomProvider. + * This generator returns a fixed value. The value is incremented by jumping. + */ + private static class JumpableGenerator implements ArbitrarilyJumpableUniformRandomProvider { + /** The value for nextLong(). */ + private long value; + + JumpableGenerator(long seed) { + this.value = seed; + } + + @Override + public long nextLong() { + return value; + } + + @Override + public ArbitrarilyJumpableUniformRandomProvider jump(double distance) { + final JumpableGenerator copy = new JumpableGenerator(value); + // Support small distances as a long + value += (long) distance; + return copy; + } + + @Override + public ArbitrarilyJumpableUniformRandomProvider jumpPowerOfTwo(int logDistance) { + throw new IllegalStateException("Not required by default methods"); + } + } + + interface JumpsFunction { + /** + * Create a stream of generators separated by the jump distance. + * + * @param rng Jumpable generator. + * @param streamSize Number of objects to generate. + * @param distance Distance to jump forward with the state cycle. + * @return the stream + */ + Stream<ArbitrarilyJumpableUniformRandomProvider> apply(ArbitrarilyJumpableUniformRandomProvider rng, long size, double distance); + } + + /** + * Return a stream of jump arguments, each of the arguments consisting of the size of + * the stream, the seed value for the jumpable generator, and the jump distance. + * + * @return the stream of arguments + */ + static Stream<Arguments> jumpArguments() { + return Stream.of( + // size, seed + Arguments.of(0, 0, 0.0), + Arguments.of(1, 62317845757L, 2.0), + Arguments.of(5, -12683127894356L, 42.0) + ); + } + + @ParameterizedTest + @ValueSource(longs = {-1, -2, Long.MIN_VALUE}) + void testInvalidStreamSizeThrows(long size) { + final ArbitrarilyJumpableUniformRandomProvider rng = new JumpableGenerator(0); + final double distance = 10; + Assertions.assertThrows(IllegalArgumentException.class, () -> rng.jumps(size, distance)); + } + + @ParameterizedTest + @ValueSource(doubles = {-1, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, Double.NaN}) + void testInvalidDistanceThrows(double distance) { + final ArbitrarilyJumpableUniformRandomProvider rng = new JumpableGenerator(0); + final long size = 1; + Assertions.assertThrows(IllegalArgumentException.class, () -> rng.jumps(size, distance)); + } + + @ParameterizedTest + @MethodSource(value = {"jumpArguments"}) + void testJumps(int size, long seed, double distance) { + assertJumps(size, seed, distance, + (rng, n, d) -> rng.jumps(d).limit(n)); + } + + @ParameterizedTest + @MethodSource(value = {"jumpArguments"}) + void testJumpsWithSize(int size, long seed, double distance) { + assertJumps(size, seed, distance, + ArbitrarilyJumpableUniformRandomProvider::jumps); + } + + /** + * Assert that successive calls to the generator jump function will create a series of + * generators that matches the stream function. + * + * @param size Number of jumps. + * @param seed Seed for the generator. + * @param distance Jump distance. + * @param streamFunction Stream function to create a series of generators spaced + * using the jump function. + */ + private static void assertJumps(int size, long seed, double distance, + JumpsFunction streamFunction) { + // Manually jump + final JumpableGenerator jumpingRNG = new JumpableGenerator(seed); + final long[] expected = new long[size]; + for (int i = 0; i < size; i++) { + final UniformRandomProvider copy = jumpingRNG.jump(distance); + Assertions.assertNotSame(jumpingRNG, copy, "Jump function should return a copy"); + expected[i] = copy.nextLong(); + } + + // Stream (must be sequential) + final JumpableGenerator streamingRNG = new JumpableGenerator(seed); + final Stream<? extends UniformRandomProvider> stream = + streamFunction.apply(streamingRNG, size, distance); + Assertions.assertFalse(stream.isParallel(), "Jumping requires a non-parallel stream"); + + // Stream should create unique generators + final Set<UniformRandomProvider> set = new HashSet<>(); + final long[] actual = stream.map(x -> addAndReturn(set, x)) + .mapToLong(UniformRandomProvider::nextLong) + .toArray(); + Assertions.assertEquals(size, set.size(), "Stream should have unique generators"); + Assertions.assertFalse(set.contains(streamingRNG), "Stream contains the source of the stream as a generator"); + + Assertions.assertArrayEquals(expected, actual, "Stream function did not match the jump function"); + } + + /** + * Add the generator to the set and return the generator. This is a convenience + * method used to check generator objects in a stream are unique and not the same as + * the generator that created the stream. + * + * @param set Set + * @param x Generator + * @return the generator + */ + private static UniformRandomProvider addAndReturn(Set<UniformRandomProvider> set, UniformRandomProvider x) { + set.add(x); + return x; + } +} 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 0cb2cc4f..0cc3f893 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 @@ -157,8 +157,8 @@ import org.apache.commons.rng.simple.internal.SeedFactory; * non-overlapping sequences by copying the generator and then advancing a large number * of steps in the generator sequence. Repeated jumps can create a series of * child generators that will output non-overlapping sequences over a specified number - * of outputs. These implementations are identified using the {@link #isJumpable()} - * and {@link #isLongJumpable()} methods. + * of outputs. These implementations are identified using the {@link #isJumpable()}, + * {@link #isLongJumpable()} and {@link #isArbitrarilyJumpable()} methods. * </p> * <pre><code> * RandomSource source = RandomSource.XO_RO_SHI_RO_128_SS; // Known to be jumpable. @@ -802,6 +802,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.ArbitrarilyJumpableUniformRandomProvider + * ArbitrarilyJumpableUniformRandomProvider} 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.isJumpable()) { + * ArbitrarilyJumpableUniformRandomProvider rng = + * (ArbitrarilyJumpableUniformRandomProvider) source.create(); + * } + * </code></pre> + * + * @return {@code true} if arbitrarily jumpable + * @since 1.7 + */ + public boolean isArbitrarilyJumpable() { + return isAssignableTo(org.apache.commons.rng.ArbitrarilyJumpableUniformRandomProvider.class); + } + /** * Checks whether the implementing class represented by this random source * supports the {@link org.apache.commons.rng.SplittableUniformRandomProvider 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 d5fccc53..e9229c7d 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 @@ -33,6 +33,7 @@ import org.junit.jupiter.params.ParameterizedTest; import org.junit.jupiter.params.provider.MethodSource; import org.apache.commons.rng.UniformRandomProvider; +import org.apache.commons.rng.ArbitrarilyJumpableUniformRandomProvider; import org.apache.commons.rng.JumpableUniformRandomProvider; import org.apache.commons.rng.LongJumpableUniformRandomProvider; import org.apache.commons.rng.RandomProviderState; @@ -361,6 +362,9 @@ class ProvidersCommonParametricTest { Assertions.assertEquals(rng instanceof LongJumpableUniformRandomProvider, originalSource.isLongJumpable(), "isLongJumpable"); + Assertions.assertEquals(rng instanceof ArbitrarilyJumpableUniformRandomProvider, + originalSource.isArbitrarilyJumpable(), + "isArbitrarilyJumpable"); Assertions.assertEquals(rng instanceof SplittableUniformRandomProvider, originalSource.isSplittable(), "isSplittable"); 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 fe07c6bb..2d966c45 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 testIsArbitrarilyJumpable() { + Assertions.assertFalse(RandomSource.JDK.isArbitrarilyJumpable(), "JDK is not ArbitrarilyJumpable"); + Assertions.assertFalse(RandomSource.XOR_SHIFT_1024_S_PHI.isArbitrarilyJumpable(), "XOR_SHIFT_1024_S_PHI is not ArbitrarilyJumpable"); + // TODO: Add a true implementation + } + @Test void testIsSplittable() { Assertions.assertFalse(RandomSource.JDK.isSplittable(), "JDK is not Splittable"); diff --git a/src/conf/checkstyle/checkstyle-suppressions.xml b/src/conf/checkstyle/checkstyle-suppressions.xml index 31865d56..f9c106c7 100644 --- a/src/conf/checkstyle/checkstyle-suppressions.xml +++ b/src/conf/checkstyle/checkstyle-suppressions.xml @@ -28,7 +28,7 @@ <suppress checks="HiddenField" files=".*Sampler\.java$" message="'rng' hides a field." /> <!-- Methods have the names from the Spliterator interface that is implemented by child classes. Classes are package-private and should not require documentation. --> - <suppress checks="MissingJavadocMethod" files="[\\/]UniformRandomProviderSupport\.java$" lines="461-466"/> + <suppress checks="MissingJavadocMethod" files="[\\/]UniformRandomProviderSupport\.java$" lines="479-484"/> <!-- Be more lenient on tests. --> <suppress checks="Javadoc" files=".*[/\\]test[/\\].*" /> <suppress checks="MultipleStringLiterals" files=".*[/\\]test[/\\].*" />
