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 8449aa64871180bf1fb2be78264b8c3974b94c99 Author: aherbert <[email protected]> AuthorDate: Thu Sep 26 16:37:26 2019 +0100 RNG-119: Add LongJumpable support to XoShiRo generators. This adds the long jump function to those generators previously supporting only a jump function. --- .../rng/core/source32/AbstractXoShiRo128.java | 31 +++++++++++++++++++--- .../rng/core/source64/AbstractXoShiRo512.java | 31 +++++++++++++++++++--- .../org/apache/commons/rng/core/RandomAssert.java | 27 +++++++++++++++++++ .../rng/core/source32/XoShiRo128PlusTest.java | 18 +++++++++++++ .../rng/core/source32/XoShiRo128StarStarTest.java | 18 +++++++++++++ .../rng/core/source64/XoShiRo512PlusTest.java | 18 +++++++++++++ .../rng/core/source64/XoShiRo512StarStarTest.java | 19 +++++++++++++ .../commons/rng/simple/RandomSourceTest.java | 4 +-- 8 files changed, 156 insertions(+), 10 deletions(-) diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/AbstractXoShiRo128.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/AbstractXoShiRo128.java index 789613b..6bcdf78 100644 --- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/AbstractXoShiRo128.java +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/AbstractXoShiRo128.java @@ -18,6 +18,7 @@ package org.apache.commons.rng.core.source32; 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; @@ -29,13 +30,17 @@ import org.apache.commons.rng.core.util.NumberFactory; * * @since 1.3 */ -abstract class AbstractXoShiRo128 extends IntProvider implements JumpableUniformRandomProvider { +abstract class AbstractXoShiRo128 extends IntProvider implements LongJumpableUniformRandomProvider { /** Size of the state vector. */ private static final int SEED_SIZE = 4; /** The coefficients for the jump function. */ private static final int[] JUMP_COEFFICIENTS = { 0x8764000b, 0xf542d2d3, 0x6fa035c3, 0x77f2db5b }; + /** The coefficients for the long jump function. */ + private static final int[] LONG_JUMP_COEFFICIENTS = { + 0xb523952e, 0x0b6f099f, 0xccf5a0ef, 0x1c580662 + }; // State is maintained using variables rather than an array for performance @@ -135,7 +140,23 @@ abstract class AbstractXoShiRo128 extends IntProvider implements JumpableUniform @Override public UniformRandomProvider jump() { final UniformRandomProvider copy = copy(); - performJump(); + performJump(JUMP_COEFFICIENTS); + return copy; + } + + /** + * {@inheritDoc} + * + * <p>The jump size is the equivalent of 2<sup>96</sup> calls to + * {@link UniformRandomProvider#nextLong() nextLong()}. It can provide up to + * 2<sup>32</sup> non-overlapping subsequences of length 2<sup>96</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> + */ + @Override + public JumpableUniformRandomProvider longJump() { + final JumpableUniformRandomProvider copy = copy(); + performJump(LONG_JUMP_COEFFICIENTS); return copy; } @@ -148,13 +169,15 @@ abstract class AbstractXoShiRo128 extends IntProvider implements JumpableUniform /** * Perform the jump to advance the generator state. Resets the cached state of the generator. + * + * @param jumpCoefficients Jump coefficients. */ - private void performJump() { + private void performJump(int[] jumpCoefficients) { int s0 = 0; int s1 = 0; int s2 = 0; int s3 = 0; - for (final int jc : JUMP_COEFFICIENTS) { + for (final int jc : jumpCoefficients) { for (int b = 0; b < 32; b++) { if ((jc & (1 << b)) != 0) { s0 ^= state0; diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/AbstractXoShiRo512.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/AbstractXoShiRo512.java index a654a2d..d4f5be2 100644 --- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/AbstractXoShiRo512.java +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/AbstractXoShiRo512.java @@ -18,6 +18,7 @@ package org.apache.commons.rng.core.source64; 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; @@ -29,7 +30,7 @@ import org.apache.commons.rng.core.util.NumberFactory; * * @since 1.3 */ -abstract class AbstractXoShiRo512 extends LongProvider implements JumpableUniformRandomProvider { +abstract class AbstractXoShiRo512 extends LongProvider implements LongJumpableUniformRandomProvider { /** Size of the state vector. */ private static final int SEED_SIZE = 8; /** The coefficients for the jump function. */ @@ -37,6 +38,11 @@ abstract class AbstractXoShiRo512 extends LongProvider implements JumpableUnifor 0x33ed89b6e7a353f9L, 0x760083d7955323beL, 0x2837f2fbb5f22faeL, 0x4b8c5674d309511cL, 0xb11ac47a7ba28c25L, 0xf1be7667092bcc1cL, 0x53851efdb6df0aafL, 0x1ebbc8b23eaf25dbL }; + /** The coefficients for the long jump function. */ + private static final long[] LONG_JUMP_COEFFICIENTS = { + 0x11467fef8f921d28L, 0xa2a819f2e79c8ea8L, 0xa8299fc284b3959aL, 0xb4d347340ca63ee1L, + 0x1cb0940bedbff6ceL, 0xd956c5c4fa1f8e17L, 0x915e38fd4eda93bcL, 0x5b3ccdfa5d7daca5L + }; // State is maintained using variables rather than an array for performance @@ -162,11 +168,26 @@ abstract class AbstractXoShiRo512 extends LongProvider implements JumpableUnifor @Override public UniformRandomProvider jump() { final UniformRandomProvider copy = copy(); - performJump(); + performJump(JUMP_COEFFICIENTS); return copy; } /** + * {@inheritDoc} + * + * <p>The jump size is the equivalent of 2<sup>384</sup> calls to + * {@link UniformRandomProvider#nextLong() nextLong()}. It can provide up to + * 2<sup>128</sup> non-overlapping subsequences of length 2<sup>384</sup>; each + * subsequence can provide up to 2<sup>128</sup> non-overlapping subsequences of + * length 2<sup>256</sup>using the {@link #jump()} method.</p> + */ + @Override + public JumpableUniformRandomProvider longJump() { + final JumpableUniformRandomProvider copy = copy(); + performJump(LONG_JUMP_COEFFICIENTS); + return copy; + } + /** * Create a copy. * * @return the copy @@ -175,8 +196,10 @@ abstract class AbstractXoShiRo512 extends LongProvider implements JumpableUnifor /** * Perform the jump to advance the generator state. Resets the cached state of the generator. + * + * @param jumpCoefficients Jump coefficients. */ - private void performJump() { + private void performJump(long[] jumpCoefficients) { long s0 = 0; long s1 = 0; long s2 = 0; @@ -185,7 +208,7 @@ abstract class AbstractXoShiRo512 extends LongProvider implements JumpableUnifor long s5 = 0; long s6 = 0; long s7 = 0; - for (final long jc : JUMP_COEFFICIENTS) { + for (final long jc : jumpCoefficients) { for (int b = 0; b < 64; b++) { if ((jc & (1L << b)) != 0) { s0 ^= state0; 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 19b4ecd..8bb388c 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 @@ -154,6 +154,33 @@ public final class RandomAssert { * @param expectedAfter Expected output after the long jump. * @param rng Random generator. */ + public static void assertLongJumpEquals(int[] expectedBefore, + int[] expectedAfter, + LongJumpableUniformRandomProvider rng) { + final UniformRandomProvider copy = rng.longJump(); + Assert.assertNotSame("The copy instance should be a different object", rng, copy); + Assert.assertEquals("The copy instance should be the same class", rng.getClass(), copy.getClass()); + assertEquals("Pre-jump value at position ", expectedBefore, copy); + assertEquals("Post-jump value at position ", expectedAfter, rng); + } + + /** + * Assert that the random generator satisfies the contract of the + * {@link LongJumpableUniformRandomProvider#longJump()} function. + * + * <ul> + * <li>The long jump returns a copy instance. This is asserted to be a different object + * of the same class type as the input. + * <li>The copy instance outputs the expected sequence for the current state of the input generator. + * This is asserted using the {@code expectedBefore} sequence. + * <li>The input instance outputs the expected sequence for an advanced state. + * This is asserted using the {@code expectedAfter} sequence. + * <ul> + * + * @param expectedBefore Expected output before the long jump. + * @param expectedAfter Expected output after the long jump. + * @param rng Random generator. + */ public static void assertLongJumpEquals(long[] expectedBefore, long[] expectedAfter, LongJumpableUniformRandomProvider rng) { diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/XoShiRo128PlusTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/XoShiRo128PlusTest.java index 0a83ebf..cc1d70e 100644 --- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/XoShiRo128PlusTest.java +++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/XoShiRo128PlusTest.java @@ -58,6 +58,19 @@ public class XoShiRo128PlusTest { 0xc8682b75, 0xb1831941, 0xf0c50a84, 0x7321dc33, }; + private static final int[] EXPECTED_SEQUENCE_AFTER_LONG_JUMP = { + 0x93572bc7, 0xc46a6c83, 0x5803ee73, 0x525cc155, + 0x45d27ce5, 0xfffbdf72, 0x764d4d47, 0xe94e5ee4, + 0xf91b0e1f, 0x63138833, 0xb63f1a97, 0x5cf78346, + 0xad979a8f, 0xcf4c0d3f, 0xccfb1798, 0xff978ea1, + 0xc7744b7c, 0xfcae345e, 0x40618bc9, 0x55f2ffd7, + 0x869ad599, 0x0101eba4, 0x5091a478, 0xc82b9461, + 0x940e4e36, 0x49f41fbe, 0x6005f4af, 0x6cf46dab, + 0x2de3bc75, 0x06530e45, 0x839ef4b3, 0xd2510032, + 0x6053afee, 0xe67eb5e8, 0x2f25e700, 0x2de3212b, + 0x41cf6954, 0xa66d8fd8, 0x6c348704, 0xb16b8da5, + }; + @Test public void testReferenceCode() { RandomAssert.assertEquals(EXPECTED_SEQUENCE, new XoShiRo128Plus(SEED)); @@ -91,4 +104,9 @@ public class XoShiRo128PlusTest { public void testJump() { RandomAssert.assertJumpEquals(EXPECTED_SEQUENCE, EXPECTED_SEQUENCE_AFTER_JUMP, new XoShiRo128Plus(SEED)); } + + @Test + public void testLongJump() { + RandomAssert.assertLongJumpEquals(EXPECTED_SEQUENCE, EXPECTED_SEQUENCE_AFTER_LONG_JUMP, new XoShiRo128Plus(SEED)); + } } diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/XoShiRo128StarStarTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/XoShiRo128StarStarTest.java index eba120b..1eb6242 100644 --- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/XoShiRo128StarStarTest.java +++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/XoShiRo128StarStarTest.java @@ -58,6 +58,19 @@ public class XoShiRo128StarStarTest { 0x58339082, 0x6f7ac9ed, 0xf07faa96, 0x7348dcbf, }; + private static final int[] EXPECTED_SEQUENCE_AFTER_LONG_JUMP = { + 0x84ea405d, 0xe43ec9b9, 0x7b43546a, 0x5aeca3cb, + 0x54ec4005, 0x90511268, 0x63a1d86b, 0x56e93375, + 0x64a6fd02, 0x559acfe7, 0xf4f18034, 0x70c3ae88, + 0xfc5d0b08, 0xecba359e, 0x00784b22, 0x48627c78, + 0xa971ad76, 0x07d938c2, 0x4db234d7, 0xcafbf946, + 0x6b716c5d, 0xc0275fc2, 0x158f8407, 0x4e41c342, + 0x1480ac03, 0x6932767a, 0x31eed7c1, 0x9cee78df, + 0x2c5d98f5, 0x04d1aab9, 0xbd1a4b49, 0xa40820b9, + 0x9384d31f, 0x35dab84f, 0xd6067813, 0xa45e9b4e, + 0x13ec0f47, 0x1f3df575, 0x358f3a61, 0xf210c90e, + }; + @Test public void testReferenceCode() { RandomAssert.assertEquals(EXPECTED_SEQUENCE, new XoShiRo128StarStar(SEED)); @@ -91,4 +104,9 @@ public class XoShiRo128StarStarTest { public void testJump() { RandomAssert.assertJumpEquals(EXPECTED_SEQUENCE, EXPECTED_SEQUENCE_AFTER_JUMP, new XoShiRo128StarStar(SEED)); } + + @Test + public void testLongJump() { + RandomAssert.assertLongJumpEquals(EXPECTED_SEQUENCE, EXPECTED_SEQUENCE_AFTER_LONG_JUMP, new XoShiRo128StarStar(SEED)); + } } diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/XoShiRo512PlusTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/XoShiRo512PlusTest.java index ac679a6..68ced8b 100644 --- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/XoShiRo512PlusTest.java +++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/XoShiRo512PlusTest.java @@ -59,6 +59,19 @@ public class XoShiRo512PlusTest { 0xb0389318ac95388fL, 0x12c69799c7c33350L, 0x7e37dbd8210b480cL, 0xf3ab8bf173c83485L, }; + private static final long[] EXPECTED_SEQUENCE_AFTER_LONG_JUMP = { + 0x98ec0fe940d88036L, 0x3e52a613181661d2L, 0xeb21cca2c39a958aL, 0x54ebdbbcf454bc00L, + 0x35b40a46c5a2db60L, 0xba92b5b8ec604df6L, 0xb8a9d151e1de068cL, 0xf932e23c318739c7L, + 0x7d37ce0d0251a4f9L, 0x3294c0651c007662L, 0x3baa7ebc5883451dL, 0x5f074c651e12f539L, + 0x173759a4f89afd6fL, 0xb84f6162c377111cL, 0x8ff2ae4a11140c3bL, 0x90f58d08cd59d92bL, + 0x3a3fc7591a19dc9cL, 0x7abde79e2d744124L, 0xb501dcc26191260dL, 0xc579a01d3b8060e7L, + 0x44f8ff268669152bL, 0xa64fc5f1793acc93L, 0xe8e846be0146eeacL, 0x78508943a2f9f185L, + 0x8ac83b0956d74f6dL, 0x9b2edb8573b06d42L, 0x7043f31d7d3b0072L, 0xcef8bdd056a672aeL, + 0xa598d8ca8da699baL, 0xd3f4d5229fcd63e0L, 0xc32969e1c8b3344bL, 0x5cd49a0984c25cbeL, + 0xe611854c41080e47L, 0x2bb80e455908083dL, 0x76b63c69756b1c60L, 0xf1b5cb3e99e921b7L, + 0x3eec38ebbff82d51L, 0xf0d1900eb73cf3c0L, 0x0d852253155da740L, 0xa0b237932c01e9eaL, + }; + @Test public void testReferenceCode() { RandomAssert.assertEquals(EXPECTED_SEQUENCE, new XoShiRo512Plus(SEED)); @@ -93,4 +106,9 @@ public class XoShiRo512PlusTest { public void testJump() { RandomAssert.assertJumpEquals(EXPECTED_SEQUENCE, EXPECTED_SEQUENCE_AFTER_JUMP, new XoShiRo512Plus(SEED)); } + + @Test + public void testLongJump() { + RandomAssert.assertLongJumpEquals(EXPECTED_SEQUENCE, EXPECTED_SEQUENCE_AFTER_LONG_JUMP, new XoShiRo512Plus(SEED)); + } } diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/XoShiRo512StarStarTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/XoShiRo512StarStarTest.java index dcf1fcb..8334ad4 100644 --- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/XoShiRo512StarStarTest.java +++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/XoShiRo512StarStarTest.java @@ -59,6 +59,20 @@ public class XoShiRo512StarStarTest { 0x2f1f49ee5e1d5207L, 0xafca316bd4672318L, 0x91e9df4fe8cb3cddL, 0x8857a767c3a1d387L, }; + + private static final long[] EXPECTED_SEQUENCE_AFTER_LONG_JUMP = { + 0x1d1aaa6cb41463c7L, 0xf37f8d9edc99e22fL, 0xa9f678cc5b0519acL, 0xcfe2d9024aede22fL, + 0x1ba8d18326d7c87eL, 0xcdd7d8c3fcc9d409L, 0x270738c721177babL, 0xaebe345f36cbfef9L, + 0xece8a978e6d76e43L, 0x6e4aaa9e351488c7L, 0x4ed730591155ad3cL, 0x374d8de2429482feL, + 0x1d8ff3451265eee2L, 0x3e74d38a2e3d2994L, 0xfb9aec450dbf9ba1L, 0x70120a3d50950b7eL, + 0xe48a3a80393a2203L, 0xb50eb0af3bb7e9f5L, 0xb778f992ecea024fL, 0xce7b77bca13db0c3L, + 0x7b579d90909ddcdcL, 0xce2d49db02b06f24L, 0x294fb69e2b1b3431L, 0xc6f9fc24c0d9d2dfL, + 0xa41564ad936d9312L, 0xa6b50f2f160adfeeL, 0x32eb7357197f57daL, 0x17bfbb289d8f2c1eL, + 0x4350c6747c718f54L, 0x21a283a2364151b2L, 0x059f807782775667L, 0xcc46db651af55502L, + 0xdeaf921ddd2f7737L, 0xcacf5eb1ed4ba4f7L, 0x7ab712770f8f2401L, 0xcae044ede9c64460L, + 0x0760c193ee64c8d3L, 0x234a3a0cb3870369L, 0x845cee292225f32dL, 0xd3bd2343d30d3057L, + }; + @Test public void testReferenceCode() { RandomAssert.assertEquals(EXPECTED_SEQUENCE, new XoShiRo512StarStar(SEED)); @@ -93,4 +107,9 @@ public class XoShiRo512StarStarTest { public void testJump() { RandomAssert.assertJumpEquals(EXPECTED_SEQUENCE, EXPECTED_SEQUENCE_AFTER_JUMP, new XoShiRo512StarStar(SEED)); } + + @Test + public void testLongJump() { + RandomAssert.assertLongJumpEquals(EXPECTED_SEQUENCE, EXPECTED_SEQUENCE_AFTER_LONG_JUMP, new XoShiRo512StarStar(SEED)); + } } 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 1155f05..5739246 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 @@ -70,14 +70,14 @@ public class RandomSourceTest { @Test public void testIsJumpable() { Assert.assertFalse("JDK is not Jumpable", RandomSource.JDK.isJumpable()); - Assert.assertTrue("XO_SHI_RO_128_SS is Jumpable", RandomSource.XO_SHI_RO_128_SS.isJumpable()); + Assert.assertTrue("XOR_SHIFT_1024_S_PHI is Jumpable", RandomSource.XOR_SHIFT_1024_S_PHI.isJumpable()); Assert.assertTrue("XO_SHI_RO_256_SS is Jumpable", RandomSource.XO_SHI_RO_256_SS.isJumpable()); } @Test public void testIsLongJumpable() { Assert.assertFalse("JDK is not LongJumpable", RandomSource.JDK.isLongJumpable()); - Assert.assertFalse("XO_SHI_RO_128_SS is not LongJumpable", RandomSource.XO_SHI_RO_128_SS.isLongJumpable()); + Assert.assertFalse("XOR_SHIFT_1024_S_PHI is not LongJumpable", RandomSource.XOR_SHIFT_1024_S_PHI.isLongJumpable()); Assert.assertTrue("XO_SHI_RO_256_SS is LongJumpable", RandomSource.XO_SHI_RO_256_SS.isLongJumpable()); } }
