You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2019/09/26 17:08:59 UTC
[commons-rng] 01/02: RNG-119: Add LongJumpable support to XoShiRo
generators.
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 <ah...@apache.org>
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());
}
}