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 4d5c7a064731df0bc04aa8e74edb6cee9ad044eb Author: Alex Herbert <[email protected]> AuthorDate: Mon Feb 16 14:26:33 2026 +0000 RNG-188: Add arbitrary jump support to Philox generators --- .../rng/core/source32/IntJumpDistances.java | 161 ++++++++++ .../commons/rng/core/source32/Philox4x32.java | 160 +++++++++- .../rng/core/source64/LongJumpDistances.java | 148 +++++++++ .../commons/rng/core/source64/Philox4x64.java | 169 +++++++++-- ...ArbitrarilyJumpableProvidersParametricTest.java | 331 +++++++++++++++++++++ .../rng/core/JumpableProvidersParametricTest.java | 77 ++++- .../org/apache/commons/rng/core/ProvidersList.java | 16 + .../org/apache/commons/rng/core/RandomAssert.java | 42 ++- .../rng/core/source32/IntJumpDistancesTest.java | 180 +++++++++++ .../commons/rng/core/source32/Philox4x32Test.java | 260 +++++++++++++++- .../rng/core/source64/LongJumpDistancesTest.java | 191 ++++++++++++ .../commons/rng/core/source64/Philox4x64Test.java | 271 ++++++++++++++++- .../commons/rng/simple/RandomSourceTest.java | 2 +- pom.xml | 1 + src/conf/pmd/pmd-ruleset.xml | 3 +- src/conf/revapi/api-changes.json | 16 + 16 files changed, 1964 insertions(+), 64 deletions(-) diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/IntJumpDistances.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/IntJumpDistances.java new file mode 100644 index 00000000..3ce5c5ea --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/IntJumpDistances.java @@ -0,0 +1,161 @@ +/* + * 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.source32; + +/** + * Utility for working with positive integer jump distances represented + * as 32-bit integers. + * + * @since 1.7 + */ +final class IntJumpDistances { + /** 2^63. */ + private static final double TWO_POW_63 = 0x1.0p63; + /** The value of the exponent for NaN when the exponent is + * extracted and scaled to account for multiplying the + * floating-point 52-bit mantissa to an integer. 1024 - 52 = 972. */ + private static final int NAN_EXP = 972; + /** Mask to extract the 52-bit mantissa from a long representation of a double. */ + private static final long MANTISSA_MASK = 0x000f_ffff_ffff_ffffL; + + /** Class contains only static methods. */ + private IntJumpDistances() {} + + /** + * Validate the jump {@code distance} is valid within the given {@code period} + * of the cycle. + * + * @param distance Jump distance. + * @param period Cycle period. + * @throws IllegalArgumentException if {@code distance} is negative, + * or is greater than the {@code period}. + */ + static void validateJump(double distance, double period) { + // Logic negation will detect NaN + if (!(distance < period && distance >= 0)) { + throw new IllegalArgumentException( + String.format("Invalid jump distance: %s (Period: %s)", distance, period)); + } + } + + /** + * Validate the jump distance of 2<sup>{@code logDistance}</sup> is valid within the + * given cycle period of 2<sup>{@code logPeriod}</sup>. + * + * <p>Note: Negative {@code logDistance} is allowed as the distance is {@code >= 0}. + * + * @param logDistance Base-2 logarithm of the distance to jump forward with the state cycle. + * @param logPeriod Base-2 logarithm of the cycle period. + * @throws IllegalArgumentException if {@code logDistance >= logPeriod}. + */ + static void validateJumpPowerOfTwo(int logDistance, int logPeriod) { + if (logDistance >= logPeriod) { + throw new IllegalArgumentException( + String.format("Invalid jump distance: 2^%d (Period: 2^%d)", logDistance, logPeriod)); + } + } + + /** + * Write the {@code value} to an unsigned integer representation. Any fractional part + * of the floating-point value is discarded. The integer part of the value must be + * positive or an exception is raised. + * + * <p>The 53-bit significand of the {@code value} is converted to an integer, shifted + * to align with a 32-bit boundary and written to the provided {@code result}, ordered + * with the least significant bits first. + * + * <p>No bounds checking is performed. The {@code result} array is assumed to have a + * length of at least 2 to store an unshifted 53-bit significand. The required array + * size for values larger than 2^53 can be computed using: + * + * <pre> + * 1 + Math.getExponent(value) / 32 + * </pre> + * + * <p>Parts of the array not used by the significand are unchanged. It is recommended + * to use a newly created array for the result. + * + * <p>Note: For jump distances validated as less than the period of an output cycle + * the result array length can be preallocated based on the maximum possible length. + * + * @param value Value + * @param result the integer representation + * @throws IllegalArgumentException if the {@code value} is negative or non-finite. + */ + static void writeUnsignedInteger(double value, int[] result) { + if (value < TWO_POW_63) { + // Case for representable integers + final long a = (long) value; + if (a < 0) { + throw new IllegalArgumentException( + "Integer value is negative: " + value); + } + // Split + result[0] = (int) a; + result[1] = (int) (a >>> 32); + return; + } + + // Large positive integer, infinity or NaN. + // Extract significand (with implicit leading 1 bit) and exponent. + // Note: sign is +1; exponent is non-zero. + // See IEEE 754 format conversion description in + // Double.longBitsToDouble. + final long bits = Double.doubleToRawLongBits(value); + final int exponent = (int) (bits >> 52) - 1075; + + // Check if finite + if (exponent == NAN_EXP) { + throw new IllegalArgumentException( + "Double value is not finite: " + value); + } + + final long significand = (bits & MANTISSA_MASK) | (1L << 52); + + // value == significand * 2**exponent + + // Return the offset to the first integer, and then the shifted significand. + // offset = exponent / 32 + final int offset = exponent >> 5; + + // Compute the remaining shift from the offset exponent (in [0, 31]). + final int shift = exponent - (offset << 5); + final int lo = (int) significand; + final int hi = (int) (significand >>> 32); + + // Write the low and high parts of the 53-bit significand + // across 3 output int values. + // Note the opposite of a left shift is an unsigned right shift + // where only the lowest 5 bits of the shift are used: + // x << n : x >>> (32 - n) == x >>> -n + // Mask the bits to right shift. This handles shift == 0. + final int mask = ~(-1 >>> shift); + final int v1 = lo << shift; + final int v2 = ((lo & mask) >>> -shift) | (hi << shift); + final int v3 = (hi & mask) >>> -shift; + + // Record the result assuming the result array is large enough + // to store the leading most significant bit. + // The 53-bit significand will write to 2 or 3 output positions + // so we must check if v3 contains the significant bit. + result[offset] = v1; + result[offset + 1] = v2; + if (v3 != 0) { + result[offset + 2] = v3; + } + } +} diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/Philox4x32.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/Philox4x32.java index 671a3be9..61c0ab07 100644 --- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/Philox4x32.java +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/Philox4x32.java @@ -17,21 +17,23 @@ package org.apache.commons.rng.core.source32; +import org.apache.commons.rng.ArbitrarilyJumpableUniformRandomProvider; import org.apache.commons.rng.JumpableUniformRandomProvider; import org.apache.commons.rng.LongJumpableUniformRandomProvider; import org.apache.commons.rng.UniformRandomProvider; import org.apache.commons.rng.core.util.NumberFactory; import java.util.Arrays; +import java.util.stream.Stream; /** * This class implements the Philox4x32 128-bit counter-based generator with 10 rounds. * * <p>This is a member of the Philox family of generators. Memory footprint is 192 bits - * and the period is 4*2<sup>128</sup>.</p> + * and the period is 2<sup>130</sup>.</p> * * <p>Jumping in the sequence is essentially instantaneous. - * This generator provides subsequences for easy parallelization. + * This generator provides both subsequences and arbitrary jumps for easy parallelization. * * <p>References: * <ol> @@ -43,7 +45,8 @@ import java.util.Arrays; * * @since 1.7 */ -public final class Philox4x32 extends IntProvider implements LongJumpableUniformRandomProvider { +public final class Philox4x32 extends IntProvider implements LongJumpableUniformRandomProvider, + ArbitrarilyJumpableUniformRandomProvider { /** Philox 32-bit mixing constant for counter 0. */ private static final int K_PHILOX_10_A = 0x9E3779B9; /** Philox 32-bit mixing constant for counter 1. */ @@ -56,6 +59,13 @@ public final class Philox4x32 extends IntProvider implements LongJumpableUniform private static final int PHILOX_BUFFER_SIZE = 4; /** Number of state variables. */ private static final int STATE_SIZE = 7; + /** The base-2 logarithm of the period. */ + private static final int LOG_PERIOD = 130; + /** The period of 2^130 as a double. */ + private static final double PERIOD = 0x1.0p130; + /** 2^54. Threshold for a double that cannot have the 2 least + * significant bits set when converted to a long. */ + private static final double TWO_POW_54 = 0x1.0p54; /** Counter 0. */ private int counter0; @@ -245,45 +255,163 @@ public final class Philox4x32 extends IntProvider implements LongJumpableUniform /** * {@inheritDoc} * - * <p>The jump size is the equivalent of 4*2<sup>64</sup> + * <p>The jump size is the equivalent of 2<sup>66</sup> * calls to {@link UniformRandomProvider#nextInt() nextInt()}. It can provide * up to 2<sup>64</sup> non-overlapping subsequences.</p> */ @Override public UniformRandomProvider jump() { - final Philox4x32 copy = copy(); + final Philox4x32 copy = new Philox4x32(this); if (++counter2 == 0) { counter3++; } - rand10(); - resetCachedState(); + finishJump(); return copy; } /** * {@inheritDoc} * - * <p>The jump size is the equivalent of 4*2<sup>96</sup> calls to + * <p>The jump size is the equivalent of 2<sup>98</sup> calls to * {@link UniformRandomProvider#nextLong() nextLong()}. It can provide up to - * 2<sup>32</sup> non-overlapping subsequences of length 4*2<sup>96</sup>; each + * 2<sup>32</sup> non-overlapping subsequences of length 2<sup>98</sup>; each * subsequence can provide up to 2<sup>32</sup> non-overlapping subsequences of - * length 2<sup>64</sup> using the {@link #jump()} method.</p> + * length 2<sup>66</sup> using the {@link #jump()} method.</p> */ @Override public JumpableUniformRandomProvider longJump() { - final Philox4x32 copy = copy(); + final Philox4x32 copy = new Philox4x32(this); counter3++; - rand10(); - resetCachedState(); + finishJump(); return copy; } + /** {@inheritDoc} */ + @Override + public ArbitrarilyJumpableUniformRandomProvider jump(double distance) { + IntJumpDistances.validateJump(distance, PERIOD); + // Decompose into an increment for the buffer position and counter + final int skip = getBufferPositionIncrement(distance); + final int[] increment = getCounterIncrement(distance); + return copyAndJump(skip, increment); + } + + /** {@inheritDoc} */ + @Override + public ArbitrarilyJumpableUniformRandomProvider jumpPowerOfTwo(int logDistance) { + IntJumpDistances.validateJumpPowerOfTwo(logDistance, LOG_PERIOD); + // For simplicity this re-uses code to increment the buffer position and counter + // when only one or the other is required for a power of 2. + // In practice the jump should be much larger than 1 and the necessary regeneration + // of the buffer is the most time consuming step. + int skip = 0; + final int[] increment = new int[PHILOX_BUFFER_SIZE]; + if (logDistance >= 0) { + if (logDistance <= 1) { + // The first 2 powers update the buffer position. + skip = 1 << logDistance; + } else { + // Remaining powers update the 128-bit counter + final int n = logDistance - 2; + // Create the increment. + // Start at n / 32 with a 1-bit shifted n % 32 + increment[n >> 5] = 1 << (n & 0x1f); + } + } + return copyAndJump(skip, increment); + } + + /** {@inheritDoc} */ + @Override + public Stream<ArbitrarilyJumpableUniformRandomProvider> jumps(double distance) { + IntJumpDistances.validateJump(distance, PERIOD); + // Decompose into an increment for the buffer position and counter + final int skip = getBufferPositionIncrement(distance); + final int[] increment = getCounterIncrement(distance); + return Stream.generate(() -> copyAndJump(skip, increment)).sequential(); + } + + /** + * Gets the buffer position increment from the jump distance. + * + * @param distance Jump distance. + * @return the buffer position increment + */ + private static int getBufferPositionIncrement(double distance) { + return distance < TWO_POW_54 ? + // 2 least significant digits from the integer representation + (int)((long) distance) & 0x3 : + 0; + } + + /** + * Gets the counter increment from the jump distance. + * + * @param distance Jump distance. + * @return the counter increment + */ + private static int[] getCounterIncrement(double distance) { + final int[] increment = new int[PHILOX_BUFFER_SIZE]; + // The counter is incremented if the distance is above the buffer size + // (increment = distance / 4). + if (distance >= PHILOX_BUFFER_SIZE) { + IntJumpDistances.writeUnsignedInteger(distance * 0.25, increment); + } + return increment; + } + /** - * Create a copy. + * Copy the generator and advance the internal state. The copy is returned. * + * <p>This method: (1) assumes that the arguments have been validated; + * and (2) regenerates the output buffer if required. + * + * @param skip Amount to skip the buffer position in [0, 3]. + * @param increment Unsigned 128-bit increment, least significant bits first. * @return the copy */ - private Philox4x32 copy() { - return new Philox4x32(this); + private ArbitrarilyJumpableUniformRandomProvider copyAndJump(int skip, int[] increment) { + final Philox4x32 copy = new Philox4x32(this); + + // Skip the buffer position forward. + // Assumes position is in [0, 4] and skip is less than 4. + // Handle rollover but allow position=4 to regenerate buffer on next output call. + bufferPosition += skip; + if (bufferPosition > PHILOX_BUFFER_SIZE) { + bufferPosition -= PHILOX_BUFFER_SIZE; + incrementCounter(); + } + + // Increment the 128-bit counter. + // Addition using unsigned int as longs. + // Any overflow bit is carried to the next counter. + // Unrolled branchless loop for performance. + long r; + r = (counter0 & 0xffff_ffffL) + (increment[0] & 0xffff_ffffL); + counter0 = (int) r; + r = (counter1 & 0xffff_ffffL) + (increment[1] & 0xffff_ffffL) + (r >>> 32); + counter1 = (int) r; + r = (counter2 & 0xffff_ffffL) + (increment[2] & 0xffff_ffffL) + (r >>> 32); + counter2 = (int) r; + r = (counter3 & 0xffff_ffffL) + (increment[3] & 0xffff_ffffL) + (r >>> 32); + counter3 = (int) r; + + finishJump(); + return copy; + } + + /** + * Finish the jump of this generator. Resets the cached state and regenerates + * the output buffer if required. + */ + private void finishJump() { + resetCachedState(); + // Regenerate the internal buffer only if the buffer position is + // within the output buffer. Otherwise regeneration is delayed until + // next output. This allows more efficient consecutive jumping when + // the buffer is due to be regenerated. + if (bufferPosition < PHILOX_BUFFER_SIZE) { + rand10(); + } } } diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/LongJumpDistances.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/LongJumpDistances.java new file mode 100644 index 00000000..378d6e4a --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/LongJumpDistances.java @@ -0,0 +1,148 @@ +/* + * 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.source64; + +/** + * Utility for working with positive integer jump distances represented + * as 64-bit integers. + * + * @since 1.7 + */ +final class LongJumpDistances { + /** 2^63. */ + private static final double TWO_POW_63 = 0x1.0p63; + /** The value of the exponent for NaN when the exponent is + * extracted and scaled to account for multiplying the + * floating-point 52-bit mantissa to an integer. 1024 - 52 = 972. */ + private static final int NAN_EXP = 972; + /** Mask to extract the 52-bit mantissa from a long representation of a double. */ + private static final long MANTISSA_MASK = 0x000f_ffff_ffff_ffffL; + /** Small shift of a 53-bit significand where it remains within the same long. */ + private static final int SMALL_SHIFT = 11; + + /** Class contains only static methods. */ + private LongJumpDistances() {} + + /** + * Validate the jump {@code distance} is valid within the given {@code period} + * of the cycle. + * + * @param distance Jump distance. + * @param period Cycle period. + * @throws IllegalArgumentException if {@code distance} is negative, + * or is greater than the {@code period}. + */ + static void validateJump(double distance, double period) { + // Logic negation will detect NaN + if (!(distance < period && distance >= 0)) { + throw new IllegalArgumentException( + String.format("Invalid jump distance: %s (Period: %s)", distance, period)); + } + } + + /** + * Validate the jump distance of 2<sup>{@code logDistance}</sup> is valid within the + * given cycle period of 2<sup>{@code logPeriod}</sup>. + * + * <p>Note: Negative {@code logDistance} is allowed as the distance is {@code >= 0}. + * + * @param logDistance Base-2 logarithm of the distance to jump forward with the state cycle. + * @param logPeriod Base-2 logarithm of the cycle period. + * @throws IllegalArgumentException if {@code logDistance >= logPeriod}. + */ + static void validateJumpPowerOfTwo(int logDistance, int logPeriod) { + if (logDistance >= logPeriod) { + throw new IllegalArgumentException( + String.format("Invalid jump distance: 2^%d (Period: 2^%d)", logDistance, logPeriod)); + } + } + + /** + * Write the {@code value} to an unsigned integer representation. Any fractional part + * of the floating-point value is discarded. The integer part of the value must be + * positive or an exception is raised. + * + * <p>The 53-bit significand of the {@code value} is converted to an integer, shifted + * to align with a 64-bit boundary and written to the provided {@code result}, ordered + * with the least significant bits first. + * + * <p>No bounds checking is performed. The {@code result} array is assumed to have a + * length of at least 1 to store an unshifted 53-bit significand. The required array + * size for values larger than 2^53 can be computed using: + * + * <pre> + * 1 + Math.getExponent(value) / 64 + * </pre> + * + * <p>Parts of the array not used by the significand are unchanged. It is recommended + * to use a newly created array for the result. + * + * <p>Note: For jump distances validated as less than the period of an output cycle + * the result array length can be preallocated based on the maximum possible length. + * + * @param value Value + * @param result the integer representation + * @throws IllegalArgumentException if the {@code value} is negative or non-finite. + */ + static void writeUnsignedInteger(double value, long[] result) { + if (value < TWO_POW_63) { + // Case for representable integers + final long a = (long) value; + if (a < 0) { + throw new IllegalArgumentException( + "Integer value is negative: " + value); + } + result[0] = a; + return; + } + + // Large positive integer, infinity or NaN. + // Extract significand (with implicit leading 1 bit) and exponent. + // Note: sign is +1; exponent is non-zero. + // See IEEE 754 format conversion description in + // Double.longBitsToDouble. + final long bits = Double.doubleToRawLongBits(value); + final int exponent = (int) (bits >> 52) - 1075; + + // Check if finite + if (exponent == NAN_EXP) { + throw new IllegalArgumentException( + "Double value is not finite: " + value); + } + + final long significand = (bits & MANTISSA_MASK) | (1L << 52); + + // value == significand * 2**exponent + + // Return the offset to the first long, and then the shifted significand. + // offset = exponent / 64 + final int offset = exponent >> 6; + + // Compute the remaining shift from the offset exponent (in [0, 63]). + final int shift = exponent - (offset << 6); + + // Write the low and high parts of the 53-bit significand + // across the 2 output long values. + // Note the opposite of a left shift is an unsigned right shift + // where only the lowest 6 bits of the shift are used: + // x << n : x >>> (64 - n) == x >>> -n + result[offset] = significand << shift; + if (shift > SMALL_SHIFT) { + result[offset + 1] = significand >>> -shift; + } + } +} diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/Philox4x64.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/Philox4x64.java index 2dbb5f44..7bef4035 100644 --- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/Philox4x64.java +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/Philox4x64.java @@ -17,21 +17,22 @@ package org.apache.commons.rng.core.source64; +import java.util.Arrays; +import java.util.stream.Stream; +import org.apache.commons.rng.ArbitrarilyJumpableUniformRandomProvider; import org.apache.commons.rng.JumpableUniformRandomProvider; import org.apache.commons.rng.LongJumpableUniformRandomProvider; import org.apache.commons.rng.UniformRandomProvider; import org.apache.commons.rng.core.util.NumberFactory; -import java.util.Arrays; - /** * This class implements the Philox4x64 256-bit counter-based generator with 10 rounds. * * <p>This is a member of the Philox family of generators. Memory footprint is 384 bits - * and the period is 4*2<sup>256</sup>.</p> + * and the period is 2<sup>258</sup>.</p> * * <p>Jumping in the sequence is essentially instantaneous. - * This generator provides subsequences for easy parallelization. + * This generator provides both subsequences and arbitrary jumps for easy parallelization. * * <p>References: * <ol> @@ -43,7 +44,8 @@ import java.util.Arrays; * * @since 1.7 */ -public final class Philox4x64 extends LongProvider implements LongJumpableUniformRandomProvider { +public final class Philox4x64 extends LongProvider implements LongJumpableUniformRandomProvider, + ArbitrarilyJumpableUniformRandomProvider { /** Philox 32-bit mixing constant for counter 0. */ private static final long PHILOX_M0 = 0xD2E7470EE14C6C93L; /** Philox 32-bit mixing constant for counter 1. */ @@ -56,6 +58,13 @@ public final class Philox4x64 extends LongProvider implements LongJumpableUnifor private static final int PHILOX_BUFFER_SIZE = 4; /** Number of state variables. */ private static final int STATE_SIZE = 7; + /** The base-2 logarithm of the period. */ + private static final int LOG_PERIOD = 258; + /** The period of 2^258 as a double. */ + private static final double PERIOD = 0x1.0p258; + /** 2^54. Threshold for a double that cannot have the 2 least + * significant bits set when converted to a long. */ + private static final double TWO_POW_54 = 0x1.0p54; /** Counter 0. */ private long counter0; @@ -243,45 +252,169 @@ public final class Philox4x64 extends LongProvider implements LongJumpableUnifor /** * {@inheritDoc} * - * <p>The jump size is the equivalent of 4*2<sup>128</sup> + * <p>The jump size is the equivalent of 2<sup>130</sup> * calls to {@link UniformRandomProvider#nextLong() nextLong()}. It can provide * up to 2<sup>128</sup> non-overlapping subsequences.</p> */ @Override public UniformRandomProvider jump() { - final Philox4x64 copy = copy(); + final Philox4x64 copy = new Philox4x64(this); if (++counter2 == 0) { counter3++; } - rand10(); - resetCachedState(); + finishJump(); return copy; } /** * {@inheritDoc} * - * <p>The jump size is the equivalent of 4*2<sup>192</sup> calls to + * <p>The jump size is the equivalent of 2<sup>194</sup> calls to * {@link UniformRandomProvider#nextLong() nextLong()}. It can provide up to - * 2<sup>64</sup> non-overlapping subsequences of length 2<sup>192</sup>; each + * 2<sup>64</sup> non-overlapping subsequences of length 2<sup>194</sup>; each * subsequence can provide up to 2<sup>64</sup> non-overlapping subsequences of - * length 2<sup>128</sup> using the {@link #jump()} method.</p> + * length 2<sup>130</sup> using the {@link #jump()} method.</p> */ @Override public JumpableUniformRandomProvider longJump() { - final Philox4x64 copy = copy(); + final Philox4x64 copy = new Philox4x64(this); counter3++; - rand10(); - resetCachedState(); + finishJump(); return copy; } + @Override + public ArbitrarilyJumpableUniformRandomProvider jump(double distance) { + LongJumpDistances.validateJump(distance, PERIOD); + // Decompose into an increment for the buffer position and counter + final int skip = getBufferPositionIncrement(distance); + final long[] increment = getCounterIncrement(distance); + return copyAndJump(skip, increment); + } + + @Override + public ArbitrarilyJumpableUniformRandomProvider jumpPowerOfTwo(int logDistance) { + LongJumpDistances.validateJumpPowerOfTwo(logDistance, LOG_PERIOD); + // For simplicity this re-uses code to increment the buffer position and counter + // when only one or the other is required for a power of 2. + // In practice the jump should be much larger than 1 and the necessary regeneration + // of the buffer is the most time consuming step. + int skip = 0; + final long[] increment = new long[PHILOX_BUFFER_SIZE]; + if (logDistance >= 0) { + if (logDistance <= 1) { + // The first 2 powers update the buffer position. + skip = 1 << logDistance; + } else { + // Remaining powers update the 256-bit counter + final int n = logDistance - 2; + // Create the increment. + // Start at n / 64 with a 1-bit shifted n % 64 + increment[n >> 6] = 1L << (n & 0x3f); + } + } + return copyAndJump(skip, increment); + } + + /** {@inheritDoc} */ + @Override + public Stream<ArbitrarilyJumpableUniformRandomProvider> jumps(double distance) { + LongJumpDistances.validateJump(distance, PERIOD); + // Decompose into an increment for the buffer position and counter + final int skip = getBufferPositionIncrement(distance); + final long[] increment = getCounterIncrement(distance); + return Stream.generate(() -> copyAndJump(skip, increment)).sequential(); + } + + /** + * Gets the buffer position increment from the jump distance. + * + * @param distance Jump distance. + * @return the buffer position increment + */ + private static int getBufferPositionIncrement(double distance) { + return distance < TWO_POW_54 ? + // 2 least significant digits from the integer representation + (int)((long) distance) & 0x3 : + 0; + } + /** - * Create a copy. + * Gets the counter increment from the jump distance. * + * @param distance Jump distance. + * @return the counter increment + */ + private static long[] getCounterIncrement(double distance) { + final long[] increment = new long[PHILOX_BUFFER_SIZE]; + // The counter is incremented if the distance is above the buffer size + // (increment = distance / 4). + if (distance >= PHILOX_BUFFER_SIZE) { + LongJumpDistances.writeUnsignedInteger(distance * 0.25, increment); + } + return increment; + } + + /** + * Copy the generator and advance the internal state. The copy is returned. + * + * <p>This method: (1) assumes that the arguments have been validated; + * and (2) regenerates the output buffer if required. + * + * @param skip Amount to skip the buffer position in [0, 3]. + * @param increment Unsigned 256-bit increment, least significant bits first. * @return the copy */ - private Philox4x64 copy() { - return new Philox4x64(this); + private ArbitrarilyJumpableUniformRandomProvider copyAndJump(int skip, long[] increment) { + final Philox4x64 copy = new Philox4x64(this); + + // Skip the buffer position forward. + // Assumes position is in [0, 4] and skip is less than 4. + // Handle rollover but allow position=4 to regenerate buffer on next output call. + bufferPosition += skip; + if (bufferPosition > PHILOX_BUFFER_SIZE) { + bufferPosition -= PHILOX_BUFFER_SIZE; + incrementCounter(); + } + + // Increment the 256-bit counter. + // Addition using unsigned int as longs. + // Any overflow bit is carried to the next counter. + // Unrolled branchless loop for performance. + long r; + long s; + r = (counter0 & 0xffff_ffffL) + (increment[0] & 0xffff_ffffL); + s = (counter0 >>> 32) + (increment[0] >>> 32) + (r >>> 32); + counter0 = (r & 0xffff_ffffL) | (s << 32); + + r = (counter1 & 0xffff_ffffL) + (increment[1] & 0xffff_ffffL) + (s >>> 32); + s = (counter1 >>> 32) + (increment[1] >>> 32) + (r >>> 32); + counter1 = (r & 0xffff_ffffL) | (s << 32); + + r = (counter2 & 0xffff_ffffL) + (increment[2] & 0xffff_ffffL) + (s >>> 32); + s = (counter2 >>> 32) + (increment[2] >>> 32) + (r >>> 32); + counter2 = (r & 0xffff_ffffL) | (s << 32); + + r = (counter3 & 0xffff_ffffL) + (increment[3] & 0xffff_ffffL) + (s >>> 32); + s = (counter3 >>> 32) + (increment[3] >>> 32) + (r >>> 32); + counter3 = (r & 0xffff_ffffL) | (s << 32); + + finishJump(); + return copy; + } + + /** + * Finish the jump of this generator. Resets the cached state and regenerates + * the output buffer if required. + */ + private void finishJump() { + resetCachedState(); + // Regenerate the internal buffer only if the buffer position is + // within the output buffer. Otherwise regeneration is delayed until + // next output. This allows more efficient consecutive jumping when + // the buffer is due to be regenerated. + if (bufferPosition < PHILOX_BUFFER_SIZE) { + rand10(); + } } } diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/ArbitrarilyJumpableProvidersParametricTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/ArbitrarilyJumpableProvidersParametricTest.java new file mode 100644 index 00000000..9d7ba347 --- /dev/null +++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/ArbitrarilyJumpableProvidersParametricTest.java @@ -0,0 +1,331 @@ +/* + * 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.Arrays; +import java.util.HashSet; +import java.util.Set; +import java.util.function.ToLongFunction; +import java.util.function.UnaryOperator; +import java.util.stream.Stream; +import org.apache.commons.rng.ArbitrarilyJumpableUniformRandomProvider; +import org.apache.commons.rng.UniformRandomProvider; +import org.apache.commons.rng.core.source32.IntProvider; +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; + +/** + * Tests which all {@link ArbitrarilyJumpableUniformRandomProvider} generators must pass. + * Note: This supplements basic jump functionality tested in {@link JumpableProvidersParametricTest}. + */ +class ArbitrarilyJumpableProvidersParametricTest { + /** Negative and non-finite distances. */ + private static final double[] INVALID_DISTANCES = {Double.NaN, -1, -0.5, Double.NEGATIVE_INFINITY, + Double.POSITIVE_INFINITY}; + + 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); + } + + /** + * Gets the list of arbitrarily jumpable generators. + * + * @return the list + */ + private static Iterable<ArbitrarilyJumpableUniformRandomProvider> getArbitrarilyJumpableProviders() { + return ProvidersList.listArbitrarilyJumpable(); + } + + /** + * Test that the jump methods throw when the distance is invalid. + */ + @ParameterizedTest + @MethodSource("getArbitrarilyJumpableProviders") + void testJumpThrowsWithInvalidDistance(ArbitrarilyJumpableUniformRandomProvider generator) { + for (final double distance : INVALID_DISTANCES) { + Assertions.assertThrows(IllegalArgumentException.class, () -> generator.jump(distance)); + } + } + + /** + * Test that the random generator returned from no jump is a copy with the same output. + */ + @ParameterizedTest + @MethodSource("getArbitrarilyJumpableProviders") + void testZeroJump(ArbitrarilyJumpableUniformRandomProvider generator) { + assertZeroJump(s -> s.jump(0.0), generator); + } + + /** + * Test that the random generator returned from no jump (power of 2) is a copy with the same output. + */ + @ParameterizedTest + @MethodSource("getArbitrarilyJumpableProviders") + void testZeroJumpPowerOfTwo(ArbitrarilyJumpableUniformRandomProvider generator) { + assertZeroJump(s -> s.jumpPowerOfTwo(-1), generator); + assertZeroJump(s -> s.jumpPowerOfTwo(Integer.MIN_VALUE), generator); + } + + /** + * Assert that the random generator returned from the jump function for no distance outputs + * the same sequence. + * + * @param jumpFunction Jump function to test. + * @param generator RNG under test. + */ + private static void assertZeroJump(UnaryOperator<ArbitrarilyJumpableUniformRandomProvider> jumpFunction, + ArbitrarilyJumpableUniformRandomProvider generator) { + final UniformRandomProvider child = jumpFunction.apply(generator); + RandomAssert.assertNextLongEquals(10, generator, child); + } + + static Stream<Arguments> testSmallJump() { + final Stream.Builder<Arguments> builder = Stream.builder(); + for (final ArbitrarilyJumpableUniformRandomProvider rng : ProvidersList.listArbitrarilyJumpable()) { + // Distance forward must be strictly positive for the test + // to generate an expected sequence + for (final int size : new int[] {1, 2, 3}) { + builder.add(Arguments.of(rng, size, size)); + } + } + return builder.build(); + } + + @ParameterizedTest + @MethodSource + void testSmallJump(ArbitrarilyJumpableUniformRandomProvider generator, int distance) { + assertSmallJump(s -> s.jump(distance), distance, generator); + } + + @ParameterizedTest + @MethodSource("testSmallJump") + void testSmallJumpPowerOfTwo(ArbitrarilyJumpableUniformRandomProvider generator, int distance) { + assertSmallJump(s -> s.jumpPowerOfTwo(distance), 1 << distance, generator); + } + + /** + * Assert that the random generator returned from the jump function for the specified + * distance outputs the same sequence. The distance jumped should be small so it can be + * verified by skipping sequential output from the generator. + * + * @param jumpFunction Jump function to test. + * @param distance Distance advanced by the jump function. + * @param generator RNG under test. + */ + private static void assertSmallJump(UnaryOperator<ArbitrarilyJumpableUniformRandomProvider> jumpFunction, + int distance, + ArbitrarilyJumpableUniformRandomProvider generator) { + // Manually jump. + final ArbitrarilyJumpableUniformRandomProvider reference = copy(generator); + + // Get the primary output of the generator + final ToLongFunction<UniformRandomProvider> fun = generator instanceof IntProvider ? + UniformRandomProvider::nextInt : + UniformRandomProvider::nextLong; + + final int size = 10; + final long[] expected = new long[size]; + for (int i = 0; i < size; i++) { + expected[i] = fun.applyAsLong(reference); + // Skip forward + for (int j = 1; j < distance; j++) { + fun.applyAsLong(reference); + } + } + + final long[] actual = new long[size]; + for (int i = 0; i < size; i++) { + final UniformRandomProvider copy = jumpFunction.apply(generator); + Assertions.assertNotSame(generator, copy, "Jump function should return a copy"); + actual[i] = fun.applyAsLong(copy); + } + + Assertions.assertArrayEquals(expected, actual, "Small jump function did not match the modulo sequence"); + } + + static Stream<Arguments> testPowerOfTwoJumps() { + final Stream.Builder<Arguments> builder = Stream.builder(); + for (final ArbitrarilyJumpableUniformRandomProvider rng : ProvidersList.listArbitrarilyJumpable()) { + // Small jumps + builder.add(Arguments.of(rng, new int[] {0})); // 1 + builder.add(Arguments.of(rng, new int[] {1})); // 2 + builder.add(Arguments.of(rng, new int[] {0, 1})); // 3 + builder.add(Arguments.of(rng, new int[] {1, 3, 5})); // 42 + // Bigger jumps. Use values within a period of 2^128 + builder.add(Arguments.of(rng, new int[] {99})); + builder.add(Arguments.of(rng, new int[] {42, 67, 63})); + builder.add(Arguments.of(rng, new int[] {113, 115, 110})); + // Limit of a 53-bit mantissa + builder.add(Arguments.of(rng, new int[] {100, 100 - 52})); + } + return builder.build(); + } + + /** + * Test power of two jumps can be combined in any order and should match an equivalent + * single jump of a double distance. + */ + @ParameterizedTest + @MethodSource + void testPowerOfTwoJumps(ArbitrarilyJumpableUniformRandomProvider generator, + int[] logDistances) { + final int min = Arrays.stream(logDistances).min().getAsInt(); + final int max = Arrays.stream(logDistances).max().getAsInt(); + Assertions.assertTrue(max - min <= 52, "log-distances are too far apart for a double"); + + final ArbitrarilyJumpableUniformRandomProvider reference = copy(generator); + double distance = 0; + for (final int logDistance : logDistances) { + distance += Math.scalb(1.0, logDistance); + generator.jumpPowerOfTwo(logDistance); + } + reference.jump(distance); + RandomAssert.assertNextLongEquals(10, reference, generator); + } + + @ParameterizedTest + @MethodSource("getArbitrarilyJumpableProviders") + void testJumpsStreamSize(ArbitrarilyJumpableUniformRandomProvider generator) { + final double distance = 1.0; + for (final long size : new long[] {0, 1, 7, 13}) { + Assertions.assertEquals(size, generator.jumps(size, distance).count(), "jumps"); + } + } + + // Test adapted from stream tests in commons-rng-client-api module + + @ParameterizedTest + @MethodSource("getArbitrarilyJumpableProviders") + void testJumpsInvalidStreamSizeThrows(ArbitrarilyJumpableUniformRandomProvider rng) { + final double distance = 1.0; + Assertions.assertThrows(IllegalArgumentException.class, () -> rng.jumps(-1, distance)); + } + + @ParameterizedTest + @MethodSource("getArbitrarilyJumpableProviders") + void testJumpsInvalidDistanceThrows(ArbitrarilyJumpableUniformRandomProvider rng) { + final long streamSize = 10; + for (final double distance : INVALID_DISTANCES) { + Assertions.assertThrows(IllegalArgumentException.class, () -> rng.jumps(distance), "jumps"); + Assertions.assertThrows(IllegalArgumentException.class, () -> rng.jumps(streamSize, distance), "jumps(distance)"); + } + } + + /** + * Return a stream of jump arguments, each of the arguments consisting of: the + * generator; the size of the stream; and the jump distance. + * + * @return the stream of arguments + */ + static Stream<Arguments> jumpArguments() { + final Stream.Builder<Arguments> builder = Stream.builder(); + for (final ArbitrarilyJumpableUniformRandomProvider rng : ProvidersList.listArbitrarilyJumpable()) { + for (final int size : new int[] {0, 1, 5}) { + for (final double distance : new double[] {0, 1, 42}) { + builder.add(Arguments.of(rng, size, distance)); + } + } + } + return builder.build(); + } + + @ParameterizedTest + @MethodSource(value = {"jumpArguments"}) + void testJumps(ArbitrarilyJumpableUniformRandomProvider generator, int size, double distance) { + assertJumps(generator, size, distance, + (rng, n, d) -> rng.jumps(d).limit(n)); + } + + @ParameterizedTest + @MethodSource(value = {"jumpArguments"}) + void testJumpsWithSize(ArbitrarilyJumpableUniformRandomProvider generator, int size, double distance) { + assertJumps(generator, size, 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 distance Jump distance. + * @param streamFunction Stream function to create a series of generators spaced + * using the jump function. + */ + private static void assertJumps(ArbitrarilyJumpableUniformRandomProvider generator, int size, double distance, + JumpsFunction streamFunction) { + // Manually jump. + final ArbitrarilyJumpableUniformRandomProvider jumpingRNG = copy(generator); + 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 Stream<? extends UniformRandomProvider> stream = + streamFunction.apply(generator, 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(generator), "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; + } + + /** + * Copy the generator. + * + * @param generator Generator + * @return the copy + */ + private static ArbitrarilyJumpableUniformRandomProvider copy(ArbitrarilyJumpableUniformRandomProvider generator) { + // This exploits a jump of zero to create a copy. + // This assumption is tested in the zero jump test. + return generator.jump(0); + } +} diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/JumpableProvidersParametricTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/JumpableProvidersParametricTest.java index d786d1cd..2760a63f 100644 --- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/JumpableProvidersParametricTest.java +++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/JumpableProvidersParametricTest.java @@ -22,7 +22,7 @@ import org.junit.jupiter.params.ParameterizedTest; import org.junit.jupiter.params.provider.MethodSource; import java.util.Arrays; - +import org.apache.commons.rng.ArbitrarilyJumpableUniformRandomProvider; import org.apache.commons.rng.JumpableUniformRandomProvider; import org.apache.commons.rng.LongJumpableUniformRandomProvider; import org.apache.commons.rng.RandomProviderState; @@ -32,7 +32,7 @@ import org.apache.commons.rng.core.source32.IntProvider; import org.apache.commons.rng.core.source64.LongProvider; /** - * Tests which all {@link JumpableUniformRandomProvider} generators must pass. + * Tests which all jumpable generators must pass. */ class JumpableProvidersParametricTest { /** The default state for the IntProvider. */ @@ -54,6 +54,15 @@ class JumpableProvidersParametricTest { return ProvidersList.listJumpable(); } + /** + * Gets the list of arbitrarily Jumpable generators. + * + * @return the list + */ + private static Iterable<ArbitrarilyJumpableUniformRandomProvider> getArbitrarilyJumpableProviders() { + return ProvidersList.listArbitrarilyJumpable(); + } + /** * Gets the function using the {@link LongJumpableUniformRandomProvider#longJump()} method. * If the RNG is not long jumpable then this will raise an exception to skip the test. @@ -85,6 +94,24 @@ class JumpableProvidersParametricTest { assertJumpReturnsACopy(getLongJumpFunction(generator), generator); } + /** + * Test that the random generator returned from the long jump is a new instance of the same class. + */ + @ParameterizedTest + @MethodSource("getArbitrarilyJumpableProviders") + void testArbitraryJumpReturnsACopy(ArbitrarilyJumpableUniformRandomProvider generator) { + assertJumpReturnsACopy(() -> generator.jump(42), generator); + } + + /** + * Test that the random generator returned from the long jump is a new instance of the same class. + */ + @ParameterizedTest + @MethodSource("getArbitrarilyJumpableProviders") + void testArbitraryJumpPowerOfTwoReturnsACopy(ArbitrarilyJumpableUniformRandomProvider generator) { + assertJumpReturnsACopy(() -> generator.jumpPowerOfTwo(7), generator); + } + /** * Assert that the random generator returned from the jump function is a new instance of the same class. * @@ -92,7 +119,7 @@ class JumpableProvidersParametricTest { * @param generator RNG under test. */ private static void assertJumpReturnsACopy(TestJumpFunction jumpFunction, - JumpableUniformRandomProvider generator) { + UniformRandomProvider generator) { final UniformRandomProvider copy = jumpFunction.jump(); Assertions.assertNotSame(generator, copy, () -> generator + ": The copy instance should be a different object"); Assertions.assertEquals(generator.getClass(), copy.getClass(), () -> generator + ": The copy instance should be the same class"); @@ -118,6 +145,26 @@ class JumpableProvidersParametricTest { assertCopyMatchesPreJumpState(getLongJumpFunction(generator), generator); } + /** + * Test that the random generator state of the copy instance returned from the arbitrary jump + * matches the input state. + */ + @ParameterizedTest + @MethodSource("getArbitrarilyJumpableProviders") + void testArbitraryJumpCopyMatchesPreJumpState(ArbitrarilyJumpableUniformRandomProvider generator) { + assertCopyMatchesPreJumpState(() -> generator.jump(42), generator); + } + + /** + * Test that the random generator state of the copy instance returned from the arbitrary jump + * matches the input state. + */ + @ParameterizedTest + @MethodSource("getArbitrarilyJumpableProviders") + void testArbitraryJumpPowerOfTwoCopyMatchesPreJumpState(ArbitrarilyJumpableUniformRandomProvider generator) { + assertCopyMatchesPreJumpState(() -> generator.jumpPowerOfTwo(7), generator); + } + /** * Assert that the random generator state of the copy instance returned from the jump * function matches the input state. @@ -138,7 +185,7 @@ class JumpableProvidersParametricTest { * @param generator RNG under test. */ private static void assertCopyMatchesPreJumpState(TestJumpFunction jumpFunction, - JumpableUniformRandomProvider generator) { + UniformRandomProvider generator) { Assumptions.assumeTrue(generator instanceof RestorableUniformRandomProvider, () -> generator + ": Not a restorable RNG"); for (int repeats = 0; repeats < 2; repeats++) { @@ -182,6 +229,26 @@ class JumpableProvidersParametricTest { assertJumpResetsDefaultState(getLongJumpFunction(generator), generator); } + /** + * Test that an arbitrary jump resets the state of the default implementation of a generator in + * {@link IntProvider} and {@link LongProvider}. + */ + @ParameterizedTest + @MethodSource("getArbitrarilyJumpableProviders") + void testArbitraryJumpResetsDefaultState(ArbitrarilyJumpableUniformRandomProvider generator) { + assertJumpResetsDefaultState(() -> generator.jump(42), generator); + } + + /** + * Test that an arbitrary jump resets the state of the default implementation of a generator in + * {@link IntProvider} and {@link LongProvider}. + */ + @ParameterizedTest + @MethodSource("getArbitrarilyJumpableProviders") + void testArbitraryJumpPowerOfTwoResetsDefaultState(ArbitrarilyJumpableUniformRandomProvider generator) { + assertJumpResetsDefaultState(() -> generator.jumpPowerOfTwo(7), generator); + } + /** * Assert the jump resets the specified number of bytes of the state. The bytes are * checked from the end of the saved state. @@ -193,7 +260,7 @@ class JumpableProvidersParametricTest { * @param generator RNG under test. */ private static void assertJumpResetsDefaultState(TestJumpFunction jumpFunction, - JumpableUniformRandomProvider generator) { + UniformRandomProvider generator) { byte[] expected; if (generator instanceof IntProvider) { expected = INT_PROVIDER_STATE; 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 47b93928..128f595c 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.L64X256Mix; import org.apache.commons.rng.core.source64.MersenneTwister64; import org.apache.commons.rng.core.source64.PcgRxsMXs64; import org.apache.commons.rng.core.source64.DotyHumphreySmallFastCounting64; +import org.apache.commons.rng.ArbitrarilyJumpableUniformRandomProvider; import org.apache.commons.rng.JumpableUniformRandomProvider; import org.apache.commons.rng.RestorableUniformRandomProvider; import org.apache.commons.rng.SplittableUniformRandomProvider; @@ -98,6 +99,8 @@ public final class ProvidersList { private static final List<JumpableUniformRandomProvider> LIST_JUMP = new ArrayList<>(); /** List of {@link SplittableUniformRandomProvider} RNGs. */ private static final List<SplittableUniformRandomProvider> LIST_SPLIT = new ArrayList<>(); + /** List of {@link ArbitrarilyJumpableUniformRandomProvider} RNGs. */ + private static final List<ArbitrarilyJumpableUniformRandomProvider> LIST_ARBITRARY = new ArrayList<>(); static { // External generator for creating a random seed. @@ -180,6 +183,9 @@ public final class ProvidersList { LIST.stream() .filter(SplittableUniformRandomProvider.class::isInstance) .forEach(rng -> LIST_SPLIT.add((SplittableUniformRandomProvider) rng)); + LIST.stream() + .filter(ArbitrarilyJumpableUniformRandomProvider.class::isInstance) + .forEach(rng -> LIST_ARBITRARY.add((ArbitrarilyJumpableUniformRandomProvider) rng)); } catch (final Exception e) { // CHECKSTYLE: stop Regexp System.err.println("Unexpected exception while creating the list of generators: " + e); @@ -243,4 +249,14 @@ public final class ProvidersList { public static Iterable<SplittableUniformRandomProvider> listSplittable() { return Collections.unmodifiableList(LIST_SPLIT); } + + /** + * Subclasses that are "parametric" tests can forward the call to + * the "@Parameters"-annotated method to this method. + * + * @return the list of {@link ArbitrarilyJumpableUniformRandomProvider} generators. + */ + public static Iterable<ArbitrarilyJumpableUniformRandomProvider> listArbitrarilyJumpable() { + return Collections.unmodifiableList(LIST_ARBITRARY); + } } 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 8a7f0db2..102919d4 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 @@ -21,7 +21,7 @@ import org.junit.jupiter.api.Assertions; import java.lang.reflect.Constructor; import java.lang.reflect.InvocationTargetException; - +import java.util.function.Supplier; import org.apache.commons.rng.JumpableUniformRandomProvider; import org.apache.commons.rng.LongJumpableUniformRandomProvider; import org.apache.commons.rng.UniformRandomProvider; @@ -229,6 +229,26 @@ public final class RandomAssert { } } + /** + * Assert that the two random generators produce the same output for + * {@link UniformRandomProvider#nextInt()} over the given number of cycles. + * The {@code message} is appended to the details of the generators and the + * cycle output position. + * + * @param cycles Number of cycles. + * @param rng1 Random generator 1. + * @param rng2 Random generator 2. + * @param message Message. + */ + public static void assertNextIntEquals(int cycles, UniformRandomProvider rng1, UniformRandomProvider rng2, + Supplier<String> message) { + for (int i = 0; i < cycles; i++) { + final int index = i; + Assertions.assertEquals(rng1.nextInt(), rng2.nextInt(), + () -> String.format("%s vs %s: Value at position %d. %s", rng1, rng2, index, message.get())); + } + } + /** * Assert that the two random generators produce the same output for * {@link UniformRandomProvider#nextLong()} over the given number of cycles. @@ -245,6 +265,26 @@ public final class RandomAssert { } } + /** + * Assert that the two random generators produce the same output for + * {@link UniformRandomProvider#nextLong()} over the given number of cycles. + * The {@code message} is appended to the details of the generators and the + * cycle output position. + * + * @param cycles Number of cycles. + * @param rng1 Random generator 1. + * @param rng2 Random generator 2. + * @param message Message. + */ + public static void assertNextLongEquals(int cycles, UniformRandomProvider rng1, UniformRandomProvider rng2, + Supplier<String> message) { + for (int i = 0; i < cycles; i++) { + final int index = i; + Assertions.assertEquals(rng1.nextLong(), rng2.nextLong(), + () -> String.format("%s vs %s: Value at position %d. %s", rng1, rng2, index, message.get())); + } + } + /** * Assert that the two random generators produce a different 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/source32/IntJumpDistancesTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/IntJumpDistancesTest.java new file mode 100644 index 00000000..6f5e4ad2 --- /dev/null +++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/IntJumpDistancesTest.java @@ -0,0 +1,180 @@ +/* + * 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.source32; + +import java.math.BigDecimal; +import java.math.BigInteger; +import java.util.Arrays; +import java.util.SplittableRandom; +import java.util.stream.DoubleStream; +import java.util.stream.DoubleStream.Builder; +import org.junit.jupiter.api.Assertions; +import org.junit.jupiter.params.ParameterizedTest; +import org.junit.jupiter.params.provider.MethodSource; +import org.junit.jupiter.params.provider.ValueSource; + +/** + * Tests for the {@link IntJumpDistances} class. + */ +class IntJumpDistancesTest { + @ParameterizedTest + @ValueSource(doubles = {-1, -123e45, + Double.POSITIVE_INFINITY, Double.NaN, Double.NEGATIVE_INFINITY}) + void testWriteUnsignedIntegerThrows(double x) { + final int[] result = new int[2]; + Assertions.assertThrows(IllegalArgumentException.class, () -> IntJumpDistances.writeUnsignedInteger(x, result)); + } + + @ParameterizedTest + @ValueSource(doubles = {0, 0.5, 1, 2, 1.23, 14, 1234L << 30, + 0x1p16, 0x1p32, 0x1.0p52, 0x1.0p56, 0x1.p63, 0x1p66, 0x1.0p128, 0x1p512, 0x1.0p1023, + 1.25687e6, 4.5828e34, 5.678923e190, 9.23678268423647e74, + Double.MAX_VALUE, + // Jump values that align with 32-bits + (1L << 52) + 1, + ((1L << 52) + 1) * 0x1.0p32, + ((1L << 52) + 1) * 0x1.0p64, + // No low 32-bits + 8.307674973655724e34, + // Random jump values for Philox4x32 that align with 32-bits + 3.839035871160997e35 * 0.25, 4.7836764219450716e35 * 0.25 + }) + @MethodSource + void testWriteUnsignedInteger(double x) { + Assertions.assertTrue(x >= 0, "Value must be positive"); + + final int[] expected = toIntArray(x); + // Result array is assumed to be correct length but at least 2 + int[] actual = new int[Math.max(2, 1 + Math.getExponent(x) / 32)]; + //int[] actual = new int[Math.max(2, expected.length)]; + IntJumpDistances.writeUnsignedInteger(x, actual); + // Trailing zeros should be unwritten + if (actual.length > expected.length) { + Assertions.assertEquals(2, actual.length, "Minimum result array size"); + for (int i = expected.length; i < actual.length; i++) { + Assertions.assertEquals(0, actual[i], "Trailing values should be zero"); + } + actual = Arrays.copyOf(actual, expected.length); + } + Assertions.assertArrayEquals(expected, actual); + } + + /** + * Provide a stream of the test values for double conversion to an integer. + * + * @return the stream + */ + static DoubleStream testWriteUnsignedInteger() { + final SplittableRandom rng = new SplittableRandom(); + final Builder builder = DoubleStream.builder(); + builder.add(Math.nextUp(0x1p63)); + builder.add(Math.nextDown(0x1p64)); + builder.add(Math.nextUp(0x1p64)); + // Create doubles with significand of different lengths. + // When aligned across boundaries that are a multiple of 32-bits + // the different length significands test all possible + // outputs of 1, 2, or 3 int values to represent the significand. + final long expBits = Double.doubleToRawLongBits(1.0); + for (final int remove : new int[] {0, 10, 20, 30, 51}) { + final long mask = ~((1L << remove) - 1); + for (int i = 0; i < 5; i++) { + // x in [1, 2) + final long bits = expBits | (rng.nextLong() >>> 12); + // Mask out insignificant bits + double x = Double.longBitsToDouble(bits & mask); + Assertions.assertTrue(x >= 1.0 && x < 2.0); + // Representable as a long + builder.add(x * 0x1.0p53); + builder.add(x * 0x1.0p51); + builder.add(x * 0x1.0p25); + // Scale so the 53-bit significand is aligned across + // the 2^96 boundary, or just before it. + x *= 0x1.0p90; + for (int j = Integer.SIZE; --j >= 0;) { + builder.add(x); + x *= 2; + } + } + } + return builder.build(); + } + + /** + * Convert the {@code value} to an integer representation. + * + * <p>The returned value contains the 53-bit significand of the + * {@code value} converted to an integer. The full representation + * is a {@code int[]} with the least significant bits first. + * This array may be padded with leading zeros for large input values. + * <pre> + * |----|----|----|---x|xxxx|xxx-| + * |----|----|xxxx|xxx-| + * |----|----|xxxx| + * </pre> + * + * @param value Value + * @return the representation + */ + private static int[] toIntArray(double value) { + return toIntArray(new BigDecimal(value).toBigInteger()); + } + + /** + * Convert the {@code value} to an integer representation. + * + * <p>The returned value contains magnitude of the + * {@code value} converted to an integer. The full representation + * is a {@code int[]} with the least significant bits first. + * + * <p>The special case of zero is returned as []. + * + * @param value Value + * @return the representation + * @throws AssertionError if the value is negative + */ + static int[] toIntArray(BigInteger value) { + // Currently this assumes the value is not negative + Assertions.assertTrue(value.signum() >= 0, "Value must be positive"); + + final int bits = value.bitLength(); + final int n = (int) Math.ceil(bits / 32.0); + final int[] result = new int[n]; + for (int i = 0; i < n; i++) { + // The value is positive so the intValue will not + // add leading 1-bits due to sign extension + result[i] = value.shiftRight(i * Integer.SIZE).intValue(); + } + return result; + } + + /** + * Convert the {@code value} to a BigInteger. + * + * <p>The value contains an unsigned integer magnitude with the least significant bits first. + * + * @param value Value + * @return the BigInteger + */ + static BigInteger toBigInteger(int[] value) { + BigInteger result = BigInteger.ZERO; + for (int i = 0; i < value.length; i++) { + result = result.add( + BigInteger.valueOf(Integer.toUnsignedLong(value[i])).shiftLeft(i * Integer.SIZE)); + } + return result; + } +} diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/Philox4x32Test.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/Philox4x32Test.java index d66a37e0..9f3966e3 100644 --- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/Philox4x32Test.java +++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/Philox4x32Test.java @@ -16,14 +16,19 @@ */ package org.apache.commons.rng.core.source32; -import java.util.stream.Stream.Builder; +import java.math.BigDecimal; +import java.math.BigInteger; import java.util.Arrays; +import java.util.SplittableRandom; import java.util.stream.Stream; +import java.util.stream.Stream.Builder; import org.apache.commons.rng.core.RandomAssert; +import org.junit.jupiter.api.Assertions; 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; +import org.junit.jupiter.params.provider.ValueSource; public class Philox4x32Test { // Data from python 3.12.12 using randomgen v2.3.0, e.g. @@ -243,7 +248,6 @@ public class Philox4x32Test { return builder.build(); } - @ParameterizedTest @MethodSource void testInternalCounter(int[] seed1, int[] seed2) { @@ -274,22 +278,254 @@ public class Philox4x32Test { @Test void testJumpCounter() { - Philox4x32 rng = new Philox4x32(new int[] {1234, 0, -1, 0, -1, 0}); - rng.jump(); + Philox4x32 rng1 = new Philox4x32(new int[] {1234, 0, -1, 0, -1, 0}); + rng1.jump(); Philox4x32 rng2 = new Philox4x32(new int[] {1234, 0, -1, 0, 0, 1}); - RandomAssert.assertNextIntEquals(10, rng, rng2); + RandomAssert.assertNextIntEquals(10, rng1, rng2); - rng = new Philox4x32(new int[] {1234, 0, -1, -1, -1, 0}); - rng.jump(); + rng1 = new Philox4x32(new int[] {1234, 0, -1, -1, -1, 0}); + rng1.jump(); rng2 = new Philox4x32(new int[] {1234, 0, -1, -1, 0, 1}); - RandomAssert.assertNextLongEquals(10, rng, rng2); + RandomAssert.assertNextIntEquals(10, rng1, rng2); } @Test void testLongJumpCounter() { - Philox4x32 rng = new Philox4x32(new int[] {1234, 0, -1, -1, -1, 0}); - rng.longJump(); - Philox4x32 rng2 = new Philox4x32(new int[] {1234, 0, -1, -1, -1, 1}); - RandomAssert.assertNextIntEquals(10, rng, rng2); + final Philox4x32 rng1 = new Philox4x32(new int[] {1234, 0, -1, -1, -1, 0}); + rng1.longJump(); + final Philox4x32 rng2 = new Philox4x32(new int[] {1234, 0, -1, -1, -1, 1}); + RandomAssert.assertNextIntEquals(10, rng1, rng2); + } + + @ParameterizedTest + @ValueSource(doubles = {0x1.0p130, 0x1.0p456, Double.MAX_VALUE}) + void testJumpThrowsWithInvalidDistance(double distance) { + final Philox4x32 rng = new Philox4x32(new int[] {1234}); + Assertions.assertThrows(IllegalArgumentException.class, () -> rng.jump(distance)); + } + + @ParameterizedTest + @ValueSource(ints = {130, 456, Integer.MAX_VALUE}) + void testJumpPowerOfTwoThrowsWithInvalidDistance(int logDistance) { + final Philox4x32 rng = new Philox4x32(new int[] {1234}); + Assertions.assertThrows(IllegalArgumentException.class, () -> rng.jumpPowerOfTwo(logDistance)); + } + + @ParameterizedTest + @MethodSource(value = "testJump") + void testArbitraryJumpMatchesJump(int[] seed, int[] ignored, int[] ignored2) { + for (int i = 0; i <= 4; i++) { + final Philox4x32 rng1 = skip(new Philox4x32(seed), i); + final Philox4x32 rng2 = skip(new Philox4x32(seed), i); + rng1.jump(); + rng2.jump(0x1.0p66); + RandomAssert.assertNextIntEquals(10, rng1, rng2); + } + } + + @ParameterizedTest + @MethodSource(value = "testJump") + void testArbitraryJumpPowerOfTwoMatchesJump(int[] seed, int[] ignored, int[] ignored2) { + for (int i = 0; i <= 4; i++) { + final Philox4x32 rng1 = skip(new Philox4x32(seed), i); + final Philox4x32 rng2 = skip(new Philox4x32(seed), i); + rng1.jump(); + rng2.jumpPowerOfTwo(66); + RandomAssert.assertNextIntEquals(10, rng1, rng2); + } + } + + @ParameterizedTest + @MethodSource(value = "testJump") + void testArbitraryJumpMatchesLongJump(int[] seed, int[] ignored, int[] ignored2) { + for (int i = 0; i <= 4; i++) { + final Philox4x32 rng1 = skip(new Philox4x32(seed), i); + final Philox4x32 rng2 = skip(new Philox4x32(seed), i); + rng1.longJump(); + rng2.jump(0x1.0p98); + RandomAssert.assertNextIntEquals(10, rng1, rng2); + } + } + + @ParameterizedTest + @MethodSource(value = "testJump") + void testArbitraryJumpPowerOfTwoMatchesLongJump(int[] seed, int[] ignored, int[] ignored2) { + for (int i = 0; i <= 4; i++) { + final Philox4x32 rng1 = skip(new Philox4x32(seed), i); + final Philox4x32 rng2 = skip(new Philox4x32(seed), i); + rng1.longJump(); + rng2.jumpPowerOfTwo(98); + RandomAssert.assertNextIntEquals(10, rng1, rng2); + } + } + + @ParameterizedTest + @MethodSource + void testArbitraryJumpCounter(int[] seed1, double distance, int[] seed2) { + // Test the buffer in a used and partially used state + for (int i = 0; i < 2; i++) { + final Philox4x32 rng1 = skip(new Philox4x32(seed1), i); + final Philox4x32 rng2 = skip(new Philox4x32(seed2), i); + rng1.jump(distance); + RandomAssert.assertNextLongEquals(10, rng1, rng2, + () -> String.format("seed=%s, distance=%s", Arrays.toString(seed1), distance)); + } + } + + static Stream<Arguments> testArbitraryJumpCounter() { + // Test of counter increment. Note that the value of -1 is all bits set and incrementing + // will carry a 1-bit to the next counter up. + final int key0 = (int) 67280421310721L; + final int key1 = (int) (67280421310721L >>> 32); + + final Stream.Builder<Arguments> builder = Stream.builder(); + + // Any power of two jump can be expressed as a double + testArbitraryJumpPowerOfTwoCounter().map(Arguments::get).forEach(objects -> { + final int logDistance = (int) objects[1]; + final double distance = Math.scalb(1.0, logDistance); + builder.add(Arguments.of(objects[0], distance, objects[2])); + }); + + // Largest allowed jump + builder.add(Arguments.of(new int[] {key0, key1, 0, 0, 0, 0}, Math.nextDown(0x1.0p130), + new int[] {key0, key1, 0, 0, -1 << 11, -1})); + + // Arbitrary jumps + builder.add(Arguments.of(new int[] {key0, key1, 0, 0, 0, 0}, 0x1.0p99 + 0x1.0p73, + new int[] {key0, key1, 0, 0, 1 << 7, 2})); + builder.add(Arguments.of(new int[] {key0, key1, 0, 0, -1, 0}, 0x1.0p99 + 0x1.0p73, + new int[] {key0, key1, 0, 0, -1 + (1 << 7), 3})); + builder.add(Arguments.of(new int[] {key0, key1, 0, 0, -1, 0}, 0x1.0p73 + 0x1.0p23, + new int[] {key0, key1, 1 << 21, 0, -1 + (1 << 7), 1})); + builder.add(Arguments.of(new int[] {key0, key1, 0, 0, 0, 0}, 1234 * 4 + 5678 * 0x1.0p34, + new int[] {key0, key1, 1234, 5678, 0, 0})); + + final SplittableRandom rng = new SplittableRandom(); + for (int i = 0; i < 10; i++) { + final int[] counter1 = rng.ints(4).toArray(); + // Jump in range [0, 2^128): 128 - 63 = 65 + final double counterDistance = Math.abs(Math.scalb((double) rng.nextLong(), rng.nextInt(65))); + final BigInteger jump = new BigDecimal(counterDistance).toBigInteger(); + final int[] counter2 = add(counter1, jump); + builder.add(Arguments.of(new int[] {key0, key1, counter1[0], counter1[1], counter1[2], counter1[3]}, + jump.doubleValue() * 4, + new int[] {key0, key1, counter2[0], counter2[1], counter2[2], counter2[3]})); + } + return builder.build(); + } + + @ParameterizedTest + @MethodSource + void testArbitraryJumpPowerOfTwoCounter(int[] seed1, int logDistance, int[] seed2) { + // Test the buffer in a used and partially used state + for (int i = 0; i < 2; i++) { + final Philox4x32 rng1 = skip(new Philox4x32(seed1), i); + final Philox4x32 rng2 = skip(new Philox4x32(seed2), i); + rng1.jumpPowerOfTwo(logDistance); + RandomAssert.assertNextLongEquals(10, rng1, rng2, + () -> String.format("seed=%s, logDistance=%d", Arrays.toString(seed1), logDistance)); + } + } + + static Stream<Arguments> testArbitraryJumpPowerOfTwoCounter() { + // Test of counter increment. Note that the value of -1 is all bits set and incrementing + // will carry a 1-bit to the next counter up. + final int key0 = (int) 67280421310721L; + final int key1 = (int) (67280421310721L >>> 32); + + final Stream.Builder<Arguments> builder = Stream.builder(); + // Jumps for each part of the counter + builder.add(Arguments.of(new int[] {key0, key1, 0, 0, 0, 0}, 2, + new int[] {key0, key1, 1, 0, 0, 0})); + builder.add(Arguments.of(new int[] {key0, key1, 0, 0, 0, 0}, 32, + new int[] {key0, key1, 1 << 30, 0, 0, 0})); + builder.add(Arguments.of(new int[] {key0, key1, 0, 0, 0, 0}, 53, + new int[] {key0, key1, 0, 1 << 19, 0, 0})); + builder.add(Arguments.of(new int[] {key0, key1, 0, 0, 0, 0}, 75, + new int[] {key0, key1, 0, 0, 1 << 9, 0})); + builder.add(Arguments.of(new int[] {key0, key1, 0, 0, 0, 0}, 99, + new int[] {key0, key1, 0, 0, 0, 2})); + // Largest jump does not wrap the overflow bit. It should be lost + // to the unrepresented 129-th bit of the counter. + builder.add(Arguments.of(new int[] {key0, key1, -1, -1, -1, -1}, 129, + new int[] {key0, key1, -1, -1, -1, -1 + (1 << 31)})); + // Roll-over by incrementing the counter by 1. + // Note that the Philox counter is incremented by 1 upon first call to regenerate + // the output buffer. The test aims to use the jump to rollover the bits + // so the counter must be initialised 1 before the rollover threshold, + // i.e. -2 + 1 (increment) + 1 (jump) == 0 + rollover. + // The test uses a variable skip forward of the generator to cover cases of counter + // increment before or after jump increment. + builder.add(Arguments.of(new int[] {key0, key1, -2, 0, 0, 0}, 2, + new int[] {key0, key1, -1, 0, 0, 0})); + builder.add(Arguments.of(new int[] {key0, key1, -2, -1, 0, 0}, 2, + new int[] {key0, key1, -1, -1, 0, 0})); + builder.add(Arguments.of(new int[] {key0, key1, -2, -1, -1, 0}, 2, + new int[] {key0, key1, -1, -1, -1, 0})); + builder.add(Arguments.of(new int[] {key0, key1, -2, -1, -1, -1}, 2, + new int[] {key0, key1, -1, -1, -1, -1})); + // Arbitrary jumps + final SplittableRandom rng = new SplittableRandom(); + for (int i = 0; i < 10; i++) { + final int[] counter1 = rng.ints(4).toArray(); + // Jump in range [0, 2^128) + final int logDistance = rng.nextInt(128); + final BigInteger jump = BigInteger.ONE.shiftLeft(logDistance); + final int[] counter2 = add(counter1, jump); + builder.add(Arguments.of(new int[] {key0, key1, counter1[0], counter1[1], counter1[2], counter1[3]}, + logDistance + 2, + new int[] {key0, key1, counter2[0], counter2[1], counter2[2], counter2[3]})); + } + return builder.build(); + } + + /** + * Test arbitrary jumps with the internal state of the generator anywhere in the + * output buffer. The jump targets both the counter increment (distance [4, 2^51)) + * and the output buffer position (distance [0, 4)). + */ + @ParameterizedTest + @MethodSource + void testArbitraryJumpCounterWithSkip(int[] seed1, long distance, int[] seed2) { + Assertions.assertNotEquals((double) distance, distance + 1.0, + "Small distance required to allow jumping within the buffer position"); + // Skip within the generator output buffer + for (int i = 0; i <= 4; i++) { + // Jump within the generator output buffer + for (int j = 0; j <= 4; j++) { + final Philox4x32 rng1 = skip(new Philox4x32(seed1), i); + final Philox4x32 rng2 = skip(new Philox4x32(seed2), i + j); + rng1.jump(distance + j); + RandomAssert.assertNextIntEquals(10, rng1, rng2, + () -> String.format("seed=%s, distance=%s", Arrays.toString(seed1), distance)); + } + } + } + + static Stream<Arguments> testArbitraryJumpCounterWithSkip() { + final int key0 = (int) 67280421310721L; + final int key1 = (int) (67280421310721L >>> 32); + + final Stream.Builder<Arguments> builder = Stream.builder(); + final SplittableRandom rng = new SplittableRandom(); + for (int i = 0; i < 5; i++) { + final int[] counter1 = rng.ints(4).toArray(); + // Jump in range [0, 2^51) + final long counterDistance = rng.nextLong(1L << 51); + final BigInteger jump = BigInteger.valueOf(counterDistance); + final int[] counter2 = add(counter1, jump); + builder.add(Arguments.of(new int[] {key0, key1, counter1[0], counter1[1], counter1[2], counter1[3]}, + counterDistance * 4, + new int[] {key0, key1, counter2[0], counter2[1], counter2[2], counter2[3]})); + } + return builder.build(); + } + + private static int[] add(int[] counter, BigInteger jump) { + final BigInteger sum = IntJumpDistancesTest.toBigInteger(counter).add(jump); + final int[] value = IntJumpDistancesTest.toIntArray(sum); + // Return result with the same counter size + return Arrays.copyOf(value, counter.length); } } diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/LongJumpDistancesTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/LongJumpDistancesTest.java new file mode 100644 index 00000000..17e8c636 --- /dev/null +++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/LongJumpDistancesTest.java @@ -0,0 +1,191 @@ +/* + * 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.source64; + +import java.math.BigDecimal; +import java.math.BigInteger; +import java.util.Arrays; +import java.util.SplittableRandom; +import java.util.stream.DoubleStream; +import java.util.stream.DoubleStream.Builder; +import org.junit.jupiter.api.Assertions; +import org.junit.jupiter.params.ParameterizedTest; +import org.junit.jupiter.params.provider.MethodSource; +import org.junit.jupiter.params.provider.ValueSource; + +/** + * Tests for the {@link LongJumpDistances} class. + */ +class LongJumpDistancesTest { + @ParameterizedTest + @ValueSource(doubles = {-1, -123e45, + Double.POSITIVE_INFINITY, Double.NaN, Double.NEGATIVE_INFINITY}) + void testWriteUnsignedIntegerThrows(double x) { + final long[] result = new long[1]; + Assertions.assertThrows(IllegalArgumentException.class, () -> LongJumpDistances.writeUnsignedInteger(x, result)); + } + + @ParameterizedTest + @ValueSource(doubles = {0, 0.5, 1, 2, 1.23, 14, 1234L << 30, + 0x1p16, 0x1p32, 0x1.0p52, 0x1.0p56, 0x1.p63, 0x1p66, 0x1.0p128, 0x1p512, 0x1.0p1023, + 1.25687e6, 4.5828e34, 5.678923e190, 9.23678268423647e74, + Double.MAX_VALUE, + // Jump values that align with 32-bits + (1L << 52) + 1, + ((1L << 52) + 1) * 0x1.0p32, + ((1L << 52) + 1) * 0x1.0p64, + // No low 32-bits + 8.307674973655724e34, + // Random jump values for Philox4x32 that align with 32-bits + 3.839035871160997e35 * 0.25, 4.7836764219450716e35 * 0.25 + }) + @MethodSource + void testWriteUnsignedInteger(double x) { + Assertions.assertTrue(x >= 0, "Value must be positive"); + + final long[] expected = toLongArray(x); + // Result array is assumed to be correct length but at least 1 + long[] actual = new long[Math.max(1, 1 + Math.getExponent(x) / 64)]; + LongJumpDistances.writeUnsignedInteger(x, actual); + // Trailing zeros should be unwritten + if (actual.length > expected.length) { + Assertions.assertEquals(1, actual.length, "Minimum result array size"); + for (int i = expected.length; i < actual.length; i++) { + Assertions.assertEquals(0, actual[i], "Trailing values should be zero"); + } + actual = Arrays.copyOf(actual, expected.length); + } + Assertions.assertArrayEquals(expected, actual); + } + + /** + * Provide a stream of the test values for double conversion to an integer. + * + * @return the stream + */ + static DoubleStream testWriteUnsignedInteger() { + final SplittableRandom rng = new SplittableRandom(); + final Builder builder = DoubleStream.builder(); + builder.add(Math.nextUp(0x1p63)); + builder.add(Math.nextDown(0x1p64)); + builder.add(Math.nextUp(0x1p64)); + builder.add(Math.nextUp(0x1p127)); + builder.add(Math.nextDown(0x1p128)); + builder.add(Math.nextUp(0x1p128)); + // Create doubles with significand of different lengths. + // When aligned across boundaries that are a multiple of 64-bits + // the different length significands test all possible + // outputs of 1, 2, or 3 int values to represent the significand. + final long expBits = Double.doubleToRawLongBits(1.0); + for (final int remove : new int[] {0, 10, 20, 30, 51}) { + final long mask = ~((1L << remove) - 1); + for (int i = 0; i < 5; i++) { + // x in [1, 2) + final long bits = expBits | (rng.nextLong() >>> 12); + // Mask out insignificant bits + double x = Double.longBitsToDouble(bits & mask); + Assertions.assertTrue(x >= 1.0 && x < 2.0); + // Representable as a long + builder.add(x * 0x1.0p53); + builder.add(x * 0x1.0p51); + builder.add(x * 0x1.0p25); + // Scale so the 53-bit significand is aligned across + // the 2^128 boundary, or just before it. + x *= 0x1.0p120; + for (int j = Long.SIZE; --j >= 0;) { + builder.add(x); + x *= 2; + } + } + } + return builder.build(); + } + + /** + * Convert the {@code value} to an integer representation. + * + * <p>The returned value contains the 53-bit significand of the + * {@code value} converted to an integer. The full representation + * is a {@code long[]} with the least significant bits first. + * This array may be padded with leading zeros for large input values. + * <pre> + * |----|----|----|---x|xxxx|xxx-| + * |----|----|xxxx|xxx-| + * |----|----|xxxx| + * </pre> + * + * @param value Value + * @return the representation + */ + private static long[] toLongArray(double value) { + return toLongArray(new BigDecimal(value).toBigInteger()); + } + + /** + * Convert the {@code value} to an integer representation. + * + * <p>The returned value contains magnitude of the + * {@code value} converted to an integer. The full representation + * is a {@code int[]} with the least significant bits first. + * + * <p>The special case of zero is returned as []. + * + * @param value Value + * @return the representation + * @throws AssertionError if the value is negative + */ + static long[] toLongArray(BigInteger value) { + // Currently this assumes the value is not negative + Assertions.assertTrue(value.signum() >= 0, "Value must be positive"); + + final int bits = value.bitLength(); + final int n = (int) Math.ceil(bits / 64.0); + final long[] result = new long[n]; + for (int i = 0; i < n; i++) { + // The value is positive so the longValue will not + // add leading 1-bits due to sign extension + result[i] = value.shiftRight(i * Long.SIZE).longValue(); + } + return result; + } + + /** + * Convert the {@code value} to a BigInteger. + * + * <p>The value contains an unsigned integer magnitude with the least significant bits first. + * + * @param value Value + * @return the BigInteger + */ + static BigInteger toBigInteger(long[] value) { + BigInteger result = BigInteger.ZERO; + for (int i = 0; i < value.length; i++) { + BigInteger addend; + if (value[i] < 0) { + // Handle negative values as unsigned + addend = BigInteger.valueOf(value[i] >>> 1).shiftLeft(1); + if ((value[i] & 1) == 1) { + addend = addend.add(BigInteger.ONE); + } + } else { + addend = BigInteger.valueOf(value[i]); + } + result = result.add(addend.shiftLeft(i * Long.SIZE)); + } + return result; + } +} diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/Philox4x64Test.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/Philox4x64Test.java index 4038894e..b8aac746 100644 --- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/Philox4x64Test.java +++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/Philox4x64Test.java @@ -16,14 +16,19 @@ */ package org.apache.commons.rng.core.source64; +import java.math.BigDecimal; +import java.math.BigInteger; import java.util.Arrays; +import java.util.SplittableRandom; import java.util.stream.Stream; import java.util.stream.Stream.Builder; import org.apache.commons.rng.core.RandomAssert; +import org.junit.jupiter.api.Assertions; 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; +import org.junit.jupiter.params.provider.ValueSource; public class Philox4x64Test { // Data from python 3.12.12 using randomgen v2.3.0, e.g. @@ -345,22 +350,268 @@ public class Philox4x64Test { @Test void testJumpCounter() { - Philox4x64 rng = new Philox4x64(new long[] {1234L, 0, -1, 0, -1, 0}); - rng.jump(); + Philox4x64 rng1 = new Philox4x64(new long[] {1234L, 0, -1, 0, -1, 0}); + rng1.jump(); Philox4x64 rng2 = new Philox4x64(new long[] {1234L, 0, -1, 0, 0, 1}); - RandomAssert.assertNextLongEquals(10, rng, rng2); + RandomAssert.assertNextLongEquals(10, rng1, rng2); - rng = new Philox4x64(new long[] {1234L, 0, -1, -1, -1, 0}); - rng.jump(); + rng1 = new Philox4x64(new long[] {1234L, 0, -1, -1, -1, 0}); + rng1.jump(); rng2 = new Philox4x64(new long[] {1234L, 0, -1, -1, 0, 1}); - RandomAssert.assertNextLongEquals(10, rng, rng2); + RandomAssert.assertNextLongEquals(10, rng1, rng2); } @Test void testLongJumpCounter() { - Philox4x64 rng = new Philox4x64(new long[] {1234L, 0, -1, -1, -1, 0}); - rng.longJump(); - Philox4x64 rng2 = new Philox4x64(new long[] {1234L, 0, -1, -1, -1, 1}); - RandomAssert.assertNextLongEquals(10, rng, rng2); + final Philox4x64 rng1 = new Philox4x64(new long[] {1234L, 0, -1, -1, -1, 0}); + rng1.longJump(); + final Philox4x64 rng2 = new Philox4x64(new long[] {1234L, 0, -1, -1, -1, 1}); + RandomAssert.assertNextLongEquals(10, rng1, rng2); + } + + @ParameterizedTest + @ValueSource(doubles = {0x1.0p258, 0x1.0p456, Double.MAX_VALUE}) + void testJumpThrowsWithInvalidDistance(double distance) { + final Philox4x64 rng = new Philox4x64(new long[] {1234}); + Assertions.assertThrows(IllegalArgumentException.class, () -> rng.jump(distance)); + } + + @ParameterizedTest + @ValueSource(ints = {258, 456, Integer.MAX_VALUE}) + void testJumpPowerOfTwoThrowsWithInvalidDistance(int logDistance) { + final Philox4x64 rng = new Philox4x64(new long[] {1234}); + Assertions.assertThrows(IllegalArgumentException.class, () -> rng.jumpPowerOfTwo(logDistance)); + } + + @ParameterizedTest + @MethodSource(value = "testJump") + void testArbitraryJumpMatchesJump(long[] seed, long[] ignored, long[] ignored2) { + for (int i = 0; i <= 4; i++) { + final Philox4x64 rng1 = skip(new Philox4x64(seed), i); + final Philox4x64 rng2 = skip(new Philox4x64(seed), i); + rng1.jump(); + rng2.jump(0x1.0p130); + RandomAssert.assertNextLongEquals(10, rng1, rng2); + } + } + + @ParameterizedTest + @MethodSource(value = "testJump") + void testArbitraryJumpPowerOfTwoMatchesJump(long[] seed, long[] ignored, long[] ignored2) { + for (int i = 0; i <= 4; i++) { + final Philox4x64 rng1 = skip(new Philox4x64(seed), i); + final Philox4x64 rng2 = skip(new Philox4x64(seed), i); + rng1.jump(); + rng2.jumpPowerOfTwo(130); + RandomAssert.assertNextLongEquals(10, rng1, rng2); + } + } + + @ParameterizedTest + @MethodSource(value = "testJump") + void testArbitraryJumpMatchesLongJump(long[] seed, long[] ignored, long[] ignored2) { + for (int i = 0; i <= 4; i++) { + final Philox4x64 rng1 = skip(new Philox4x64(seed), i); + final Philox4x64 rng2 = skip(new Philox4x64(seed), i); + rng1.longJump(); + rng2.jump(0x1.0p194); + RandomAssert.assertNextLongEquals(10, rng1, rng2); + } + } + + @ParameterizedTest + @MethodSource(value = "testJump") + void testArbitraryJumpPowerOfTwoMatchesLongJump(long[] seed, long[] ignored, long[] ignored2) { + for (int i = 0; i <= 4; i++) { + final Philox4x64 rng1 = skip(new Philox4x64(seed), i); + final Philox4x64 rng2 = skip(new Philox4x64(seed), i); + rng1.longJump(); + rng2.jumpPowerOfTwo(194); + RandomAssert.assertNextLongEquals(10, rng1, rng2); + } + } + + @ParameterizedTest + @MethodSource + void testArbitraryJumpCounter(long[] seed1, double distance, long[] seed2) { + // Test the buffer in a used and partially used state + for (int i = 0; i < 2; i++) { + final Philox4x64 rng1 = skip(new Philox4x64(seed1), i); + final Philox4x64 rng2 = skip(new Philox4x64(seed2), i); + rng1.jump(distance); + RandomAssert.assertNextLongEquals(10, rng1, rng2, + () -> String.format("seed=%s, distance=%s", Arrays.toString(seed1), distance)); + } + } + + static Stream<Arguments> testArbitraryJumpCounter() { + // Test of counter increment. Note that the value of -1 is all bits set and incrementing + // will carry a 1-bit to the next counter up. + final long key0 = 67280421310721L; + final long key1 = 1234L; + + final Stream.Builder<Arguments> builder = Stream.builder(); + + // Any power of two jump can be expressed as a double + testArbitraryJumpPowerOfTwoCounter().map(Arguments::get).forEach(objects -> { + final int logDistance = (int) objects[1]; + final double distance = Math.scalb(1.0, logDistance); + builder.add(Arguments.of(objects[0], distance, objects[2])); + }); + + // Largest allowed jump + builder.add(Arguments.of(new long[] {key0, key1, 0, 0, 0, 0}, Math.nextDown(0x1.0p258), + new long[] {key0, key1, 0, 0, 0, -1L << 11})); + + // Arbitrary jumps + builder.add(Arguments.of(new long[] {key0, key1, 0, 0, 0, 0}, 0x1.0p3 + 0x1.0p40, + new long[] {key0, key1, 2 + (1L << 38), 0, 0, 0})); + builder.add(Arguments.of(new long[] {key0, key1, 0, 0, 0, 0}, 0x1.0p40 + 0x1.0p73, + new long[] {key0, key1, 1L << 38, 1 << 7, 0, 0})); + builder.add(Arguments.of(new long[] {key0, key1, 0, 0, -1, 0}, 0x1.0p195 + 0x1.0p169, + new long[] {key0, key1, 0, 0, -1 + (1L << 39), 3})); + builder.add(Arguments.of(new long[] {key0, key1, 0, -1, 0, 0}, 0x1.0p73 + 0x1.0p23, + new long[] {key0, key1, 1 << 21, -1 + (1 << 7), 1, 0})); + builder.add(Arguments.of(new long[] {key0, key1, 0, 0, 0, 0}, 1234 * 0x1.0p34 + 5678 * 0x1.0p66, + new long[] {key0, key1, 1234L << 32, 5678, 0, 0})); + + final SplittableRandom rng = new SplittableRandom(); + for (int i = 0; i < 10; i++) { + final long[] counter1 = rng.longs(4).toArray(); + // Jump in range [0, 2^256): 256 - 63 = 193 + final double counterDistance = Math.abs(Math.scalb((double) rng.nextLong(), rng.nextInt(193))); + final BigInteger jump = new BigDecimal(counterDistance).toBigInteger(); + final long[] counter2 = add(counter1, jump); + builder.add(Arguments.of(new long[] {key0, key1, counter1[0], counter1[1], counter1[2], counter1[3]}, + jump.doubleValue() * 4, + new long[] {key0, key1, counter2[0], counter2[1], counter2[2], counter2[3]})); + } + return builder.build(); + } + + @ParameterizedTest + @MethodSource + void testArbitraryJumpPowerOfTwoCounter(long[] seed1, int logDistance, long[] seed2) { + // Test the buffer in a used and partially used state + for (int i = 0; i < 2; i++) { + final Philox4x64 rng1 = skip(new Philox4x64(seed1), i); + final Philox4x64 rng2 = skip(new Philox4x64(seed2), i); + rng1.jumpPowerOfTwo(logDistance); + RandomAssert.assertNextLongEquals(10, rng1, rng2, + () -> String.format("seed=%s, logDistance=%d", Arrays.toString(seed1), logDistance)); + } + } + + static Stream<Arguments> testArbitraryJumpPowerOfTwoCounter() { + // Test of counter increment. Note that the value of -1 is all bits set and incrementing + // will carry a 1-bit to the next counter up. + final long key0 = 67280421310721L; + final long key1 = 1234L; + + final Stream.Builder<Arguments> builder = Stream.builder(); + // Jumps for each part of the counter + builder.add(Arguments.of(new long[] {key0, key1, 0, 0, 0, 0}, 2, + new long[] {key0, key1, 1, 0, 0, 0})); + builder.add(Arguments.of(new long[] {key0, key1, 0, 0, 0, 0}, 32, + new long[] {key0, key1, 1 << 30, 0, 0, 0})); + builder.add(Arguments.of(new long[] {key0, key1, 0, 0, 0, 0}, 99, + new long[] {key0, key1, 0, 1L << 33, 0, 0})); + builder.add(Arguments.of(new long[] {key0, key1, 0, 0, 0, 0}, 157, + new long[] {key0, key1, 0, 0, 1L << 27, 0})); + builder.add(Arguments.of(new long[] {key0, key1, 0, 0, 0, 0}, 244, + new long[] {key0, key1, 0, 0, 0, 1L << 50})); + // Largest jump does not wrap the overflow bit. It should be lost + // to the unrepresented 257-th bit of the counter. + builder.add(Arguments.of(new long[] {key0, key1, -1, -1, -1, -1}, 257, + new long[] {key0, key1, -1, -1, -1, -1 + (1L << 63)})); + // Roll-over by incrementing the counter by 1. + // Note that the Philox counter is incremented by 1 upon first call to regenerate + // the output buffer. This test aims to use the jump to rollover the bits + // so the counter must be initialised 1 before the rollover threshold, + // i.e. -2 + 1 (increment) + 1 (jump) == 0 + rollover. + // The test uses a variable skip forward of the generator to cover cases of counter + // increment before or after jump increment. + builder.add(Arguments.of(new long[] {key0, key1, -2, 0, 0, 0}, 2, + new long[] {key0, key1, -1, 0, 0, 0})); + builder.add(Arguments.of(new long[] {key0, key1, -2, -1, 0, 0}, 2, + new long[] {key0, key1, -1, -1, 0, 0})); + builder.add(Arguments.of(new long[] {key0, key1, -2, -1, -1, 0}, 2, + new long[] {key0, key1, -1, -1, -1, 0})); + builder.add(Arguments.of(new long[] {key0, key1, -2, -1, -1, -1}, 2, + new long[] {key0, key1, -1, -1, -1, -1})); + // Since carry addition uses 32-bit integers also test rollover within a long. + // Low should rollover to high by jump addition. + final long l = 0xffff_ffffL; + final long h = l + 1; + builder.add(Arguments.of(new long[] {key0, key1, l - 1, 0, 0, 0}, 2, + new long[] {key0, key1, h - 1, 0, 0, 0})); + builder.add(Arguments.of(new long[] {key0, key1, 0, l, 0, 0}, 66, + new long[] {key0, key1, 0, h, 0, 0})); + builder.add(Arguments.of(new long[] {key0, key1, 0, 0, l, 0}, 130, + new long[] {key0, key1, 0, 0, h, 0})); + builder.add(Arguments.of(new long[] {key0, key1, 0, 0, 0, l}, 194, + new long[] {key0, key1, 0, 0, 0, h})); + // Arbitrary jumps + final SplittableRandom rng = new SplittableRandom(); + for (int i = 0; i < 10; i++) { + final long[] counter1 = rng.longs(4).toArray(); + // Jump in range [0, 2^256) + final int logDistance = rng.nextInt(256); + final BigInteger jump = BigInteger.ONE.shiftLeft(logDistance); + final long[] counter2 = add(counter1, jump); + builder.add(Arguments.of(new long[] {key0, key1, counter1[0], counter1[1], counter1[2], counter1[3]}, + logDistance + 2, + new long[] {key0, key1, counter2[0], counter2[1], counter2[2], counter2[3]})); + } + return builder.build(); + } + + /** + * Test arbitrary jumps with the internal state of the generator anywhere in the + * output buffer. The jump targets both the counter increment (distance [4, 2^51)) + * and the output buffer position (distance [0, 4)). + */ + @ParameterizedTest + @MethodSource + void testArbitraryJumpCounterWithSkip(long[] seed1, long distance, long[] seed2) { + Assertions.assertNotEquals((double) distance, distance + 1.0, + "Small distance required to allow jumping within the buffer position"); + // Skip within the generator output buffer + for (int i = 0; i <= 4; i++) { + // Jump within the generator output buffer + for (int j = 0; j <= 4; j++) { + final Philox4x64 rng1 = skip(new Philox4x64(seed1), i); + final Philox4x64 rng2 = skip(new Philox4x64(seed2), i + j); + rng1.jump(distance + j); + RandomAssert.assertNextLongEquals(10, rng1, rng2, + () -> String.format("seed=%s, distance=%s", Arrays.toString(seed1), distance)); + } + } + } + + static Stream<Arguments> testArbitraryJumpCounterWithSkip() { + final long key0 = 67280421310721L; + final long key1 = 1234L; + + final Stream.Builder<Arguments> builder = Stream.builder(); + final SplittableRandom rng = new SplittableRandom(); + for (int i = 0; i < 5; i++) { + final long[] counter1 = rng.longs(4).toArray(); + // Jump in range [0, 2^51) + final long counterDistance = rng.nextLong(1L << 51); + final BigInteger jump = BigInteger.valueOf(counterDistance); + final long[] counter2 = add(counter1, jump); + builder.add(Arguments.of(new long[] {key0, key1, counter1[0], counter1[1], counter1[2], counter1[3]}, + counterDistance * 4, + new long[] {key0, key1, counter2[0], counter2[1], counter2[2], counter2[3]})); + } + return builder.build(); + } + + private static long[] add(long[] counter, BigInteger jump) { + final BigInteger sum = LongJumpDistancesTest.toBigInteger(counter).add(jump); + final long[] value = LongJumpDistancesTest.toLongArray(sum); + // Return result with the same counter size + return Arrays.copyOf(value, counter.length); } } 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 2d966c45..2fbaed40 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 @@ -96,7 +96,7 @@ class RandomSourceTest { 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 + Assertions.assertTrue(RandomSource.PHILOX_4X32.isArbitrarilyJumpable(), "PHILOX_4X32 is ArbitrarilyJumpable"); } @Test diff --git a/pom.xml b/pom.xml index 1558060c..a2c31fbc 100644 --- a/pom.xml +++ b/pom.xml @@ -303,6 +303,7 @@ <roots> <!-- Path to configuration in the JSON config file --> <root>1.5</root> + <root>1.7</root> </roots> </configurationFile> </analysisConfigurationFiles> diff --git a/src/conf/pmd/pmd-ruleset.xml b/src/conf/pmd/pmd-ruleset.xml index cd0e3209..94d113a7 100644 --- a/src/conf/pmd/pmd-ruleset.xml +++ b/src/conf/pmd/pmd-ruleset.xml @@ -119,7 +119,8 @@ 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='RandomStreams']"/> + or @SimpleName='UniformRandomProviderSupport' or @SimpleName='RandomStreams' + or @SimpleName='IntJumpDistances' or @SimpleName='LongJumpDistances']"/> <!-- Allow samplers to have only factory constructors --> <property name="utilityClassPattern" value="[A-Z][a-zA-Z0-9]+(Utils?|Helper|Sampler)" /> </properties> diff --git a/src/conf/revapi/api-changes.json b/src/conf/revapi/api-changes.json index 608e1140..eb42adcf 100644 --- a/src/conf/revapi/api-changes.json +++ b/src/conf/revapi/api-changes.json @@ -19,5 +19,21 @@ ] } } + ], + "1.7": [ + { + "extension": "revapi.differences", + "id": "intentional-api-changes", + "configuration": { + "differences": [ + { + "ignore": true, + "code": "java.class.externalClassExposedInAPI", + "new": "interface org.apache.commons.rng.ArbitrarilyJumpableUniformRandomProvider", + "justification": "Arbitrary jump support was added to the client API and can be used by other modules." + } + ] + } + } ] }
