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/08/06 10:42:23 UTC
[commons-rng] branch master updated (bc1801f -> 37cb26b)
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a change to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git.
from bc1801f RNG-90: Track changes.
new 7314a5a RNG-85: Added Middle-Square Weyl Sequence generator.
new 69b966f RNG-85: Added SeedUtils to allow generation of hex permutations.
new 3b4adc0 RNG-85: Add Middle Square Weyl Sequence to RandomSource enum.
new 2c550c8 RNG-85: Add MSWS to the tests.
new e03d151 RNG-85: Add custom nextLong() implementation to MSWS generator.
new 45bb529 RNG-85: Allow primitive types to correctly seed the MSWS
new 37cb26b RNG-85: Track changes.
The 7 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
.../core/source32/MiddleSquareWeylSequence.java | 137 +++++++++++++
.../org/apache/commons/rng/core/ProvidersList.java | 3 +
.../source32/MiddleSquareWeylSequenceTest.java | 98 ++++++++++
.../commons/rng/examples/jmh/BaselineSources.java | 1 +
.../rng/examples/jmh/RandomSourceValues.java | 1 +
commons-rng-simple/pom.xml | 7 +
.../apache/commons/rng/simple/RandomSource.java | 10 +-
.../rng/simple/internal/ProviderBuilder.java | 41 +++-
.../commons/rng/simple/internal/SeedUtils.java | 213 +++++++++++++++++++++
.../rng/simple/ProvidersCommonParametricTest.java | 2 +
.../apache/commons/rng/simple/ProvidersList.java | 3 +
.../commons/rng/simple/internal/SeedUtilsTest.java | 104 ++++++++++
src/changes/changes.xml | 3 +
13 files changed, 621 insertions(+), 2 deletions(-)
create mode 100644 commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequence.java
create mode 100644 commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequenceTest.java
create mode 100644 commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/SeedUtils.java
create mode 100644 commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/SeedUtilsTest.java
[commons-rng] 03/07: RNG-85: Add Middle Square Weyl Sequence to
RandomSource enum.
Posted by ah...@apache.org.
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 3b4adc05fc42c3741b6323d96359e4420ba5bd62
Author: Alex Herbert <ah...@apache.org>
AuthorDate: Mon Aug 5 11:46:37 2019 +0100
RNG-85: Add Middle Square Weyl Sequence to RandomSource enum.
The generator requires a high quality seed is generated using a custom
seeding routine.
---
.../commons/rng/examples/jmh/BaselineSources.java | 1 +
.../commons/rng/examples/jmh/RandomSourceValues.java | 1 +
.../org/apache/commons/rng/simple/RandomSource.java | 10 +++++++++-
.../commons/rng/simple/internal/ProviderBuilder.java | 19 ++++++++++++++++++-
4 files changed, 29 insertions(+), 2 deletions(-)
diff --git a/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/BaselineSources.java b/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/BaselineSources.java
index 9404e1b..b47cb31 100644
--- a/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/BaselineSources.java
+++ b/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/BaselineSources.java
@@ -92,6 +92,7 @@ public abstract class BaselineSources {
"PCG_RXS_M_XS_64",
"PCG_MCG_XSH_RR_32",
"PCG_MCG_XSH_RS_32",
+ "MSWS",
})
private String randomSourceName;
diff --git a/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/RandomSourceValues.java b/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/RandomSourceValues.java
index 9b0c6a1..449a4de 100644
--- a/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/RandomSourceValues.java
+++ b/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/RandomSourceValues.java
@@ -70,6 +70,7 @@ public class RandomSourceValues {
"PCG_RXS_M_XS_64",
"PCG_MCG_XSH_RR_32",
"PCG_MCG_XSH_RS_32",
+ "MSWS",
})
private String randomSourceName;
diff --git a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/RandomSource.java b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/RandomSource.java
index af160b3..06ac923 100644
--- a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/RandomSource.java
+++ b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/RandomSource.java
@@ -426,7 +426,15 @@ public enum RandomSource {
* <li>Native seed size: 1.</li>
* </ul>
*/
- PCG_MCG_XSH_RS_32(ProviderBuilder.RandomSourceInternal.PCG_MCG_XSH_RS_32);
+ PCG_MCG_XSH_RS_32(ProviderBuilder.RandomSourceInternal.PCG_MCG_XSH_RS_32),
+ /**
+ * Source of randomness is {@link org.apache.commons.rng.core.source32.MiddleSquareWeylSequence}.
+ * <ul>
+ * <li>Native seed type: {@code Long}.</li>
+ * <li>Native seed size: 3.</li>
+ * </ul>
+ */
+ MSWS(ProviderBuilder.RandomSourceInternal.MSWS);
/** Internal identifier. */
private final ProviderBuilder.RandomSourceInternal internalIdentifier;
diff --git a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/ProviderBuilder.java b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/ProviderBuilder.java
index d0746d8..0487b82 100644
--- a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/ProviderBuilder.java
+++ b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/ProviderBuilder.java
@@ -31,6 +31,7 @@ import org.apache.commons.rng.core.source32.Well44497a;
import org.apache.commons.rng.core.source32.Well44497b;
import org.apache.commons.rng.core.source32.ISAACRandom;
import org.apache.commons.rng.core.source32.MersenneTwister;
+import org.apache.commons.rng.core.source32.MiddleSquareWeylSequence;
import org.apache.commons.rng.core.source32.MultiplyWithCarry256;
import org.apache.commons.rng.core.source32.KISSRandom;
import org.apache.commons.rng.core.source32.XoRoShiRo64Star;
@@ -245,7 +246,23 @@ public final class ProviderBuilder {
/** Source of randomness is {@link PcgMcgXshRs32}. */
PCG_MCG_XSH_RS_32(PcgMcgXshRs32.class,
1,
- NativeSeedType.LONG);
+ NativeSeedType.LONG),
+ /** Source of randomness is {@link MiddleSquareWeylSequence}. */
+ MSWS(MiddleSquareWeylSequence.class,
+ 3,
+ NativeSeedType.LONG_ARRAY) {
+ @Override
+ Object createSeed() {
+ // This generator requires a high quality Weyl increment.
+ final long seed = SeedFactory.createLong();
+ final long increment = SeedUtils.createLongHexPermutation(new SplitMix64(seed));
+ // The initial state should not be low complexity but the Weyl
+ // state can be any number.
+ final long state = increment;
+ final long weylState = seed;
+ return new long[] {state, weylState, increment};
+ }
+ };
/** Source type. */
private final Class<? extends UniformRandomProvider> rng;
[commons-rng] 05/07: RNG-85: Add custom nextLong() implementation
to MSWS generator.
Posted by ah...@apache.org.
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 e03d15129f6f0324b787446dbbd1e2fb72adb5f7
Author: aherbert <ah...@apache.org>
AuthorDate: Mon Aug 5 13:22:38 2019 +0100
RNG-85: Add custom nextLong() implementation to MSWS generator.
---
.../rng/core/source32/MiddleSquareWeylSequence.java | 15 +++++++++++++++
.../rng/core/source32/MiddleSquareWeylSequenceTest.java | 17 +++++++++++++++++
2 files changed, 32 insertions(+)
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequence.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequence.java
index b84cd47..1df971e 100644
--- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequence.java
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequence.java
@@ -119,4 +119,19 @@ public class MiddleSquareWeylSequence extends IntProvider {
x += w += s;
return (int) (x = (x >>> 32) | (x << 32));
}
+
+ /** {@inheritDoc} */
+ @Override
+ public long nextLong() {
+ // Avoid round trip from long to int to long by performing two iterations inline
+ x *= x;
+ x += w += s;
+ final long i1 = x & 0xffffffff00000000L;
+ x = (x >>> 32) | (x << 32);
+ x *= x;
+ x += w += s;
+ final long i2 = x >>> 32;
+ x = i2 | x << 32;
+ return i1 | i2;
+ }
}
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequenceTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequenceTest.java
index 7a6c590..e9cde90 100644
--- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequenceTest.java
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequenceTest.java
@@ -17,6 +17,8 @@
package org.apache.commons.rng.core.source32;
import org.apache.commons.rng.core.RandomAssert;
+import org.apache.commons.rng.core.util.NumberFactory;
+import org.junit.Assert;
import org.junit.Test;
public class MiddleSquareWeylSequenceTest {
@@ -78,4 +80,19 @@ public class MiddleSquareWeylSequenceTest {
final MiddleSquareWeylSequence rng = new MiddleSquareWeylSequence(new long[0]);
rng.nextInt();
}
+
+ /**
+ * Test nextLong() returns two nextInt() values joined together. This tests the custom
+ * nextLong() routine in the implementation that overrides the default.
+ */
+ @Test
+ public void testNextLong() {
+ final long[] seed = {0x012de1babb3c4104L, 0xc8161b4202294965L, 0xb5ad4eceda1ce2a9L};
+ final MiddleSquareWeylSequence rng1 = new MiddleSquareWeylSequence(seed);
+ final MiddleSquareWeylSequence rng2 = new MiddleSquareWeylSequence(seed);
+ for (int i = 0; i < 50; i++) {
+ Assert.assertEquals(NumberFactory.makeLong(rng1.nextInt(), rng1.nextInt()),
+ rng2.nextLong());
+ }
+ }
}
[commons-rng] 07/07: RNG-85: Track changes.
Posted by ah...@apache.org.
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 37cb26bf20181833eb556f2762ff46c8242ae1c4
Author: aherbert <ah...@apache.org>
AuthorDate: Tue Aug 6 11:40:21 2019 +0100
RNG-85: Track changes.
---
src/changes/changes.xml | 3 +++
1 file changed, 3 insertions(+)
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index b513681..905f6a6 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -75,6 +75,9 @@ re-run tests that fail, and pass the build if they succeed
within the allotted number of reruns (the test will be marked
as 'flaky' in the report).
">
+ <action dev="aherbert" type="add" issue="RNG-85">
+ New "MiddleSquareWeylSequence" generator.
+ </action>
<action dev="aherbert" type="update" issue="RNG-90">
"BaseProvider": Updated to use faster algorithm for nextInt(int).
</action>
[commons-rng] 01/07: RNG-85: Added Middle-Square Weyl Sequence
generator.
Posted by ah...@apache.org.
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 7314a5af2dabc45303fc602f69ab054c53c92e04
Author: Alex Herbert <ah...@apache.org>
AuthorDate: Mon Aug 5 11:00:41 2019 +0100
RNG-85: Added Middle-Square Weyl Sequence generator.
---
.../core/source32/MiddleSquareWeylSequence.java | 122 +++++++++++++++++++++
.../org/apache/commons/rng/core/ProvidersList.java | 3 +
.../source32/MiddleSquareWeylSequenceTest.java | 81 ++++++++++++++
3 files changed, 206 insertions(+)
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequence.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequence.java
new file mode 100644
index 0000000..b84cd47
--- /dev/null
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequence.java
@@ -0,0 +1,122 @@
+/*
+ * 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 org.apache.commons.rng.core.util.NumberFactory;
+
+/**
+ * Middle Square Weyl Sequence Random Number Generator.
+ *
+ * <p>A fast all-purpose 32-bit generator. Memory footprint is 192 bits and the period is at least
+ * {@code 2^64}.</p>
+ *
+ * <p>Implementation is based on the paper
+ * <a href="https://arxiv.org/abs/1704.00358v3">Middle Square Weyl Sequence RNG</a>.</p>
+ *
+ * @see <a href="https://en.wikipedia.org/wiki/Middle-square_method">Middle Square Method</a>
+ *
+ * @since 1.3
+ */
+public class MiddleSquareWeylSequence extends IntProvider {
+ /** Size of the seed array. */
+ private static final int SEED_SIZE = 3;
+
+ /** State of the generator. */
+ private long x;
+ /** State of the Weyl sequence. */
+ private long w;
+ /**
+ * Increment for the Weyl sequence. This must be odd to ensure a full period.
+ *
+ * <p>This is not final to support the restore functionality.</p>
+ */
+ private long s;
+
+ /**
+ * Creates a new instance.
+ *
+ * <p>Note: The generator output quality is highly dependent on the initial seed.
+ * If the generator is seeded poorly (for example with all zeros) it is possible the
+ * generator may output zero for many cycles before the internal state recovers randomness.
+ * The seed elements are used to set:</p>
+ *
+ * <ol>
+ * <li>The state of the generator
+ * <li>The state of the Weyl sequence
+ * <li>The increment of the Weyl sequence
+ * </ol>
+ *
+ * <p>The third element is set to odd to ensure a period of at least 2<sup>64</sup>. If the
+ * increment is of low complexity then the Weyl sequence does not contribute high quality
+ * randomness. It is recommended to use a permutation of 8 hex characters for the upper
+ * and lower 32-bits of the increment.</p>
+ *
+ * <p>The state of the generator is squared during each cycle. There is a possibility that
+ * different seeds can produce the same output, for example 0 and 2<sup>32</sup> produce
+ * the same square. This can be avoided by using the high complexity Weyl increment for the
+ * state seed element.</p>
+ *
+ * @param seed Initial seed.
+ * If the length is larger than 3, only the first 3 elements will
+ * be used; if smaller, the remaining elements will be automatically set.
+ */
+ public MiddleSquareWeylSequence(long[] seed) {
+ if (seed.length < SEED_SIZE) {
+ final long[] tmp = new long[SEED_SIZE];
+ fillState(tmp, seed);
+ setSeedInternal(tmp);
+ } else {
+ setSeedInternal(seed);
+ }
+ }
+
+ /**
+ * Seeds the RNG.
+ *
+ * @param seed Seed.
+ */
+ private void setSeedInternal(long[] seed) {
+ x = seed[0];
+ w = seed[1];
+ // Ensure the increment is odd to provide a maximal period Weyl sequence.
+ this.s = seed[2] | 1L;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected byte[] getStateInternal() {
+ return composeStateInternal(NumberFactory.makeByteArray(new long[] {x, w, s}),
+ super.getStateInternal());
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected void setStateInternal(byte[] state) {
+ final byte[][] c = splitStateInternal(state, SEED_SIZE * 8);
+ setSeedInternal(NumberFactory.makeLongArray(c[0]));
+ super.setStateInternal(c[1]);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public int next() {
+ x *= x;
+ x += w += s;
+ return (int) (x = (x >>> 32) | (x << 32));
+ }
+}
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 1c00bfb..9d4b6b5 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
@@ -34,6 +34,7 @@ import org.apache.commons.rng.core.source32.Well44497a;
import org.apache.commons.rng.core.source32.Well44497b;
import org.apache.commons.rng.core.source32.ISAACRandom;
import org.apache.commons.rng.core.source32.MersenneTwister;
+import org.apache.commons.rng.core.source32.MiddleSquareWeylSequence;
import org.apache.commons.rng.core.source32.MultiplyWithCarry256;
import org.apache.commons.rng.core.source32.KISSRandom;
import org.apache.commons.rng.core.source32.PcgXshRr32;
@@ -103,6 +104,8 @@ public final class ProvidersList {
add(LIST32, new PcgXshRs32(new long[] {g.nextLong()}));
add(LIST32, new PcgMcgXshRr32(g.nextLong()));
add(LIST32, new PcgMcgXshRs32(g.nextLong()));
+ // Ensure a high complexity increment is used for the Weyl sequence
+ add(LIST32, new MiddleSquareWeylSequence(new long[] {g.nextLong(), g.nextLong(), 0xb5ad4eceda1ce2a9L}));
// ... add more here.
// "long"-based RNGs.
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequenceTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequenceTest.java
new file mode 100644
index 0000000..7a6c590
--- /dev/null
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequenceTest.java
@@ -0,0 +1,81 @@
+/*
+ * 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 org.apache.commons.rng.core.RandomAssert;
+import org.junit.Test;
+
+public class MiddleSquareWeylSequenceTest {
+ @Test
+ public void testReferenceCode() {
+ /*
+ * The data was generated using the following program based on the author's C code:
+ * https://mswsrng.wixsite.com/rand
+ *
+ * #include <stdio.h>
+ * #include <stdint.h>
+ *
+ * uint64_t x, w, s;
+ *
+ * inline static uint32_t msws() {
+ * x *= x; x += (w += s); return x = (x>>32) | (x<<32);
+ * }
+ *
+ * int main() {
+ * x = 0x012de1babb3c4104;
+ * w = 0xc8161b4202294965;
+ * s = 0xb5ad4eceda1ce2a9;
+ * for (int i=0; i<10; i++) {
+ * for (int j=0; j<4; j++) {
+ * printf("0x%08x, ", msws());
+ * }
+ * printf("\n");
+ * }
+ * }
+ */
+ final long[] seed = {0x012de1babb3c4104L, 0xc8161b4202294965L, 0xb5ad4eceda1ce2a9L};
+
+ final int[] expectedSequence = {
+ 0xe7f4010b, 0x37bdb1e7, 0x05d8934f, 0x22970c75,
+ 0xe7432a9f, 0xd157c60f, 0x26e9b5ae, 0x3dd91250,
+ 0x8dbf85f1, 0x99e3aa17, 0xcb90322b, 0x29a007e2,
+ 0x25a431fb, 0xcc612768, 0x510db5cd, 0xeb0aec2f,
+ 0x05f88c18, 0xcdb79066, 0x5222c513, 0x9075045c,
+ 0xf11a0e0e, 0x0106ab1d, 0xe2546700, 0xdf0a7656,
+ 0x170e7908, 0x17a7b775, 0x98d69720, 0x74da3b78,
+ 0x410ea18e, 0x4f708277, 0x471853e8, 0xa2cd2587,
+ 0x16238d96, 0x57653154, 0x7ecbf9c8, 0xc5dd75bf,
+ 0x32ed82a2, 0x4700e664, 0xb0ad77c9, 0xfb87df7b,
+ };
+
+ RandomAssert.assertEquals(expectedSequence, new MiddleSquareWeylSequence(seed));
+ }
+
+ /**
+ * Test the self-seeding functionality. The seeding of the generator requires a high complexity
+ * increment for the Weyl sequence. The standard test for the statistical quality of the
+ * generator uses a good increment. This test ensures the generator can be created with a seed
+ * smaller than the seed size without exception; the statistical quality of the output is not
+ * assessed and expected to be poor.
+ */
+ @Test
+ public void testSelfSeeding() {
+ // Ensure this does not throw. The output quality will be poor.
+ final MiddleSquareWeylSequence rng = new MiddleSquareWeylSequence(new long[0]);
+ rng.nextInt();
+ }
+}
[commons-rng] 04/07: RNG-85: Add MSWS to the tests.
Posted by ah...@apache.org.
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 2c550c8907856f97c0cd86c8f5f4d0d97bcebfb9
Author: Alex Herbert <ah...@apache.org>
AuthorDate: Mon Aug 5 11:52:41 2019 +0100
RNG-85: Add MSWS to the tests.
This requires an exclusion for the test of self-seeding functionality.
---
.../org/apache/commons/rng/simple/ProvidersCommonParametricTest.java | 2 ++
.../src/test/java/org/apache/commons/rng/simple/ProvidersList.java | 3 +++
2 files changed, 5 insertions(+)
diff --git a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/ProvidersCommonParametricTest.java b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/ProvidersCommonParametricTest.java
index f54345f..ff12153 100644
--- a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/ProvidersCommonParametricTest.java
+++ b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/ProvidersCommonParametricTest.java
@@ -126,6 +126,8 @@ public class ProvidersCommonParametricTest {
public void testEmptyLongArraySeed() {
final long[] empty = new long[0];
Assume.assumeTrue(originalSource.isNativeSeed(empty));
+ // The Middle-Square Weyl Sequence generator cannot self-seed
+ Assume.assumeFalse(originalSource == RandomSource.MSWS);
// Exercise the default seeding procedure.
final UniformRandomProvider rng = RandomSource.create(originalSource, empty, originalArgs);
diff --git a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/ProvidersList.java b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/ProvidersList.java
index 8884b8e..698b8c9 100644
--- a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/ProvidersList.java
+++ b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/ProvidersList.java
@@ -60,6 +60,9 @@ public final class ProvidersList {
add(LIST32, RandomSource.PCG_XSH_RS_32, new long[] {259L, 2861L});
add(LIST32, RandomSource.PCG_MCG_XSH_RS_32, 9678L);
add(LIST32, RandomSource.PCG_MCG_XSH_RR_32, 2578291L);
+ // Ensure a high complexity increment is used for the Weyl sequence otherwise
+ // it will not output random data.
+ add(LIST32, RandomSource.MSWS, new long[] {687233648L, 678656564562300L, 0xb5ad4eceda1ce2a9L});
// ... add more here.
// "long"-based RNGs.
[commons-rng] 06/07: RNG-85: Allow primitive types to correctly
seed the MSWS
Posted by ah...@apache.org.
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 45bb52996ebc089cfdadb0bf32c2eb4a5419bc7c
Author: aherbert <ah...@apache.org>
AuthorDate: Mon Aug 5 16:20:39 2019 +0100
RNG-85: Allow primitive types to correctly seed the MSWS
---
.../rng/simple/internal/ProviderBuilder.java | 26 ++++++++++++++++++++--
1 file changed, 24 insertions(+), 2 deletions(-)
diff --git a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/ProviderBuilder.java b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/ProviderBuilder.java
index 0487b82..00e6524 100644
--- a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/ProviderBuilder.java
+++ b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/ProviderBuilder.java
@@ -253,8 +253,30 @@ public final class ProviderBuilder {
NativeSeedType.LONG_ARRAY) {
@Override
Object createSeed() {
- // This generator requires a high quality Weyl increment.
- final long seed = SeedFactory.createLong();
+ return createMswsSeed(SeedFactory.createLong());
+ }
+
+ @Override
+ Object convertSeed(Object seed) {
+ // Allow seeding with primitives to generate a good seed
+ if (seed instanceof Integer) {
+ return createMswsSeed((Integer) seed);
+ } else if (seed instanceof Long) {
+ return createMswsSeed((Long) seed);
+ }
+ // Other types (e.g. the native long[]) are handled by the default conversion
+ return super.convertSeed(seed);
+ }
+
+ /**
+ * Creates the full length seed array from the input seed using the method
+ * recommended for the generator. This is a high quality Weyl increment composed
+ * of a hex character permutation.
+ *
+ * @param seed the seed
+ * @return the seed array
+ */
+ private long[] createMswsSeed(long seed) {
final long increment = SeedUtils.createLongHexPermutation(new SplitMix64(seed));
// The initial state should not be low complexity but the Weyl
// state can be any number.
[commons-rng] 02/07: RNG-85: Added SeedUtils to allow generation of
hex permutations.
Posted by ah...@apache.org.
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 69b966f3ab135fe3f507f69de3d97bbac64fb24b
Author: Alex Herbert <ah...@apache.org>
AuthorDate: Mon Aug 5 11:36:32 2019 +0100
RNG-85: Added SeedUtils to allow generation of hex permutations.
This is to be used to seed the Middle Square Weyl Sequence generator.
---
commons-rng-simple/pom.xml | 7 +
.../commons/rng/simple/internal/SeedUtils.java | 213 +++++++++++++++++++++
.../commons/rng/simple/internal/SeedUtilsTest.java | 104 ++++++++++
3 files changed, 324 insertions(+)
diff --git a/commons-rng-simple/pom.xml b/commons-rng-simple/pom.xml
index 84c3210..116c7fc 100644
--- a/commons-rng-simple/pom.xml
+++ b/commons-rng-simple/pom.xml
@@ -50,6 +50,13 @@
<artifactId>commons-rng-core</artifactId>
<version>1.3-SNAPSHOT</version>
</dependency>
+
+ <dependency>
+ <groupId>org.apache.commons</groupId>
+ <artifactId>commons-math3</artifactId>
+ <version>3.6.1</version>
+ <scope>test</scope>
+ </dependency>
</dependencies>
</project>
diff --git a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/SeedUtils.java b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/SeedUtils.java
new file mode 100644
index 0000000..5d6aa14
--- /dev/null
+++ b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/SeedUtils.java
@@ -0,0 +1,213 @@
+/*
+ * 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.simple.internal;
+
+import org.apache.commons.rng.UniformRandomProvider;
+import org.apache.commons.rng.core.util.NumberFactory;
+
+/**
+ * Utility for creating seeds.
+ */
+final class SeedUtils {
+ /** The modulus {@code 256 % 9}. */
+ private static final int MOD_09 = 256 % 9;
+ /** The modulus {@code 256 % 10}. */
+ private static final int MOD_10 = 256 % 10;
+ /** The modulus {@code 256 % 11}. */
+ private static final int MOD_11 = 256 % 11;
+ /** The modulus {@code 256 % 12}. */
+ private static final int MOD_12 = 256 % 12;
+ /** The modulus {@code 256 % 13}. */
+ private static final int MOD_13 = 256 % 13;
+ /** The modulus {@code 256 % 14}. */
+ private static final int MOD_14 = 256 % 14;
+ /** The modulus {@code 256 % 15}. */
+ private static final int MOD_15 = 256 % 15;
+ /** The 16 hex digits in an array. */
+ private static final byte[] HEX_DIGIT_ARRAY = {0xf, 0xe, 0xd, 0xc, 0xb, 0xa, 0x9, 0x8,
+ 0x7, 0x6, 0x5, 0x4, 0x3, 0x2, 0x1, 0x0};
+
+ /**
+ * Provider of unsigned 8-bit integers.
+ */
+ private static class UnsignedByteProvider {
+ /** Mask to extract the lowest 2 bits from an integer. */
+ private static final int MASK_2_BITS = 0x3;
+ /** Mask to extract the lowest 8 bits from an integer. */
+ private static final int MASK_8_BITS = 0xff;
+
+ /** Source of randomness. */
+ private final UniformRandomProvider rng;
+ /** The current 32-bits of randomness. */
+ private int bits;
+ /** The counter tracking the bits to extract. */
+ private int counter;
+
+ /**
+ * @param rng Source of randomness.
+ */
+ UnsignedByteProvider(UniformRandomProvider rng) {
+ this.rng = rng;
+ }
+
+ /**
+ * Return the next unsigned byte.
+ *
+ * @return Value in the range[0,255]
+ */
+ int nextUnsignedByte() {
+ // Every 4 bytes generate a new 32-bit value
+ final int count = counter & MASK_2_BITS;
+ counter++;
+ if (count == 0) {
+ bits = rng.nextInt();
+ // Consume the first byte
+ return bits & MASK_8_BITS;
+ }
+ // Consume a remaining byte (occurs 3 times)
+ bits >>>= 8;
+ return bits & MASK_8_BITS;
+ }
+ }
+
+ /**
+ * Class contains only static methods.
+ */
+ private SeedUtils() {}
+
+ /**
+ * Creates an {@code int} containing a permutation of 8 hex digits chosen from 16.
+ *
+ * @param rng Source of randomness.
+ * @return hex digit permutation.
+ */
+ static int createIntHexPermutation(UniformRandomProvider rng) {
+ final UnsignedByteProvider provider = new UnsignedByteProvider(rng);
+ return createUpperBitsHexPermutation(provider);
+ }
+
+ /**
+ * Creates a {@code long} containing a permutation of 8 hex digits chosen from 16 in
+ * the upper and lower 32-bits.
+ *
+ * @param rng Source of randomness.
+ * @return hex digit permutation.
+ */
+ static long createLongHexPermutation(UniformRandomProvider rng) {
+ final UnsignedByteProvider provider = new UnsignedByteProvider(rng);
+ // Extract upper bits and combine with a second sample
+ return NumberFactory.makeLong(createUpperBitsHexPermutation(provider),
+ createUpperBitsHexPermutation(provider));
+ }
+
+ /**
+ * Creates a {@code int} containing a permutation of 8 hex digits chosen from 16.
+ *
+ * @param provider Source of randomness.
+ * @return hex digit permutation.
+ */
+ private static int createUpperBitsHexPermutation(UnsignedByteProvider provider) {
+ // Compute a Fisher-Yates shuffle in-place on the 16 hex digits.
+ // Each digit is chosen uniformly from the remaining digits.
+ // The value is swapped with the current digit.
+
+ // The following is an optimised sampling algorithm that generates
+ // a uniform deviate in the range [0,n) from an unsigned byte.
+ // The expected number of samples is 256/n.
+ // This has a bias when n does not divide into 256. So samples must
+ // be rejected at a rate of (256 % n) / 256:
+ // n 256 % n Rejection rate
+ // 9 4 0.015625
+ // 10 6 0.0234375
+ // 11 3 0.01171875
+ // 12 4 0.015625
+ // 13 9 0.03515625
+ // 14 4 0.015625
+ // 15 1 0.00390625
+ // 16 0 0
+ // The probability of no rejections is 1 - (1-p15) * (1-p14) ... = 0.115
+
+ final byte[] digits = HEX_DIGIT_ARRAY.clone();
+
+ // The first digit has no bias. Get an index using a mask to avoid modulus.
+ int bits = copyToOutput(digits, 0, 15, provider.nextUnsignedByte() & 0xf);
+
+ // All remaining digits have a bias so use the rejection algorithm to find
+ // an appropriate uniform deviate in the range [0,n)
+ bits = copyToOutput(digits, bits, 14, nextUnsignedByteInRange(provider, MOD_15, 15));
+ bits = copyToOutput(digits, bits, 13, nextUnsignedByteInRange(provider, MOD_14, 14));
+ bits = copyToOutput(digits, bits, 12, nextUnsignedByteInRange(provider, MOD_13, 13));
+ bits = copyToOutput(digits, bits, 11, nextUnsignedByteInRange(provider, MOD_12, 12));
+ bits = copyToOutput(digits, bits, 10, nextUnsignedByteInRange(provider, MOD_11, 11));
+ bits = copyToOutput(digits, bits, 9, nextUnsignedByteInRange(provider, MOD_10, 10));
+ bits = copyToOutput(digits, bits, 8, nextUnsignedByteInRange(provider, MOD_09, 9));
+
+ return bits;
+ }
+
+
+ /**
+ * Get the next unsigned byte in the range {@code [0,n)} rejecting any over-represented
+ * sample value using the pre-computed modulus.
+ *
+ * <p>This algorithm is as per Lemire (2019) adapted for 8-bit arithmetic.</p>
+ *
+ * @param provider Provider of bytes.
+ * @param threshold Modulus threshold {@code 256 % n}.
+ * @param n Upper range (exclusive)
+ * @return Value.
+ * @see <a href="https://arxiv.org/abs/1805.10941">
+ * Lemire (2019): Fast Random Integer Generation in an Interval</a>
+ */
+ private static int nextUnsignedByteInRange(UnsignedByteProvider provider, int threshold, int n) {
+ // Rejection method using multiply by a fraction:
+ // n * [0, 2^8 - 1)
+ // ------------
+ // 2^8
+ // The result is mapped back to an integer and will be in the range [0, n)
+ int m;
+ do {
+ // Compute product of n * [0, 2^8 - 1)
+ m = n * provider.nextUnsignedByte();
+
+ // Test the sample uniformity.
+ } while ((m & 0xff) < threshold);
+ // Final divide by 2^8
+ return m >>> 8;
+ }
+
+ /**
+ * Copy the lower hex digit to the output bits. Swap the upper hex digit into
+ * the lower position. This is equivalent to a swap step of a Fisher-Yates shuffle on
+ * an array but the output of the shuffle are written to the bits.
+ *
+ * @param digits Digits.
+ * @param bits Bits.
+ * @param upper Upper index.
+ * @param lower Lower index.
+ * @return Updated bits.
+ */
+ private static int copyToOutput(byte[] digits, int bits, int upper, int lower) {
+ // Move the existing bits up and append the next hex digit.
+ // This is equivalent to swapping lower to upper.
+ final int newbits = bits << 4 | digits[lower] & 0xf;
+ // Swap upper to lower.
+ digits[lower] = digits[upper];
+ return newbits;
+ }
+}
diff --git a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/SeedUtilsTest.java b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/SeedUtilsTest.java
new file mode 100644
index 0000000..412cc8c
--- /dev/null
+++ b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/SeedUtilsTest.java
@@ -0,0 +1,104 @@
+/*
+ * 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.simple.internal;
+
+import org.apache.commons.math3.stat.inference.ChiSquareTest;
+import org.apache.commons.rng.UniformRandomProvider;
+import org.apache.commons.rng.core.source64.SplitMix64;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.Arrays;
+
+/**
+ * Tests for the {@link SeedUtils}.
+ */
+public class SeedUtilsTest {
+ /**
+ * Test the int hex permutation has 8 unique hex digits per permutation.
+ * A uniformity test is performed on to check each hex digits is used evenly at each
+ * character position.
+ */
+ @Test
+ public void testCreateIntHexPermutation() {
+ final UniformRandomProvider rng = new SplitMix64(-567435247L);
+ final long[][] samples = new long[8][16];
+ for (int i = 0; i < 1000; i++) {
+ int sample = SeedUtils.createIntHexPermutation(rng);
+ int observed = 0;
+ for (int j = 0; j < 8; j++) {
+ final int digit = sample & 0xf;
+ Assert.assertEquals("Duplicate digit in sample", 0, observed & (1 << digit));
+ observed |= 1 << digit;
+ samples[j][digit]++;
+ sample >>>= 4;
+ }
+ }
+
+ final ChiSquareTest chiSquareTest = new ChiSquareTest();
+ final double[] expected = new double[16];
+ Arrays.fill(expected, 1.0 / 16);
+ // Pass if we cannot reject null hypothesis that distributions are the same.
+ for (int j = 0; j < 8; j++) {
+ Assert.assertFalse("Not uniform in digit " + j,
+ chiSquareTest.chiSquareTest(expected, samples[j], 0.001));
+ }
+ }
+
+ /**
+ * Test the long hex permutation has 8 unique hex digits per permutation in the upper and
+ * lower 32-bits.
+ * A uniformity test is performed on to check each hex digits is used evenly at each
+ * character position.
+ */
+ @Test
+ public void testCreateLongHexPermutation() {
+ final UniformRandomProvider rng = new SplitMix64(34645768L);
+ final long[][] samples = new long[16][16];
+ for (int i = 0; i < 1000; i++) {
+ long sample = SeedUtils.createLongHexPermutation(rng);
+ // Check lower 32-bits
+ long observed = 0;
+ for (int j = 0; j < 8; j++) {
+ final int digit = (int) (sample & 0xfL);
+ Assert.assertEquals("Duplicate digit in lower sample", 0, observed & (1 << digit));
+ observed |= 1 << digit;
+ samples[j][digit]++;
+ sample >>>= 4;
+ }
+ // Check upper 32-bits
+ observed = 0;
+ for (int j = 8; j < 16; j++) {
+ final int digit = (int) (sample & 0xfL);
+ Assert.assertEquals("Duplicate digit in upper sample", 0, observed & (1 << digit));
+ observed |= 1 << digit;
+ samples[j][digit]++;
+ sample >>>= 4;
+ }
+ }
+
+ final ChiSquareTest chiSquareTest = new ChiSquareTest();
+ final double[] expected = new double[16];
+ Arrays.fill(expected, 1.0 / 16);
+ // Pass if we cannot reject null hypothesis that distributions are the same.
+ for (int j = 0; j < 16; j++) {
+ Assert.assertFalse("Not uniform in digit " + j,
+ chiSquareTest.chiSquareTest(expected, samples[j], 0.001));
+ }
+ }
+}