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/28 11:19:40 UTC
[commons-rng] 01/02: RNG-112: Add Small Fast Chaotic (SFC) PRNG.
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 873069d8cd95e6a23d12f46d526539250d40e1c8
Author: aherbert <ah...@apache.org>
AuthorDate: Tue Aug 27 15:10:02 2019 +0100
RNG-112: Add Small Fast Chaotic (SFC) PRNG.
---
.../apache/commons/rng/core/source32/SFC32.java | 107 +++++++++++++++++++++
.../apache/commons/rng/core/source64/SFC64.java | 107 +++++++++++++++++++++
.../org/apache/commons/rng/core/ProvidersList.java | 4 +
.../commons/rng/core/source32/SFC32Test.java | 46 +++++++++
.../commons/rng/core/source64/SFC64Test.java | 46 +++++++++
.../commons/rng/examples/jmh/BaselineSources.java | 2 +
.../rng/examples/jmh/RandomSourceValues.java | 2 +
.../apache/commons/rng/simple/RandomSource.java | 18 +++-
.../rng/simple/internal/ProviderBuilder.java | 12 ++-
.../apache/commons/rng/simple/ProvidersList.java | 2 +
10 files changed, 344 insertions(+), 2 deletions(-)
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/SFC32.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/SFC32.java
new file mode 100644
index 0000000..384086d
--- /dev/null
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/SFC32.java
@@ -0,0 +1,107 @@
+/*
+ * 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;
+
+/**
+ * Implement the Small, Fast, Chaotic (SFC) 32-bit generator of Chris Doty-Humphrey.
+ * The original source is the PractRand test suite by the same author.
+ *
+ * <p>The state size is 128-bits; the period is a minimum of 2<sup>32</sup> and an
+ * average of approximately 2<sup>127</sup>.</p>
+ *
+ * @see <a href="http://pracrand.sourceforge.net/">PractRand</a>
+ *
+ * @since 1.3
+ */
+public class SFC32 extends IntProvider {
+ /** Size of the seed. */
+ private static final int SEED_SIZE = 3;
+
+ /** State a. */
+ private int a;
+ /** State b. */
+ private int b;
+ /** State c. */
+ private int c;
+ /** Counter. */
+ private int counter;
+
+ /**
+ * Creates an instance with the given seed.
+ *
+ * @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 SFC32(int[] seed) {
+ if (seed.length < SEED_SIZE) {
+ final int[] state = new int[SEED_SIZE];
+ fillState(state, seed);
+ setSeedInternal(state);
+ } else {
+ setSeedInternal(seed);
+ }
+ }
+
+ /**
+ * Seeds the RNG.
+ *
+ * @param seed Seed.
+ */
+ private void setSeedInternal(int[] seed) {
+ a = seed[0];
+ b = seed[1];
+ c = seed[2];
+ counter = 1;
+ for (int i = 0; i < 15; i++) {
+ next();
+ }
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public final int next() {
+ final int tmp = a + b + counter++;
+ a = b ^ (b >>> 9);
+ b = c + (c << 3);
+ c = Integer.rotateLeft(c, 21) + tmp;
+ return tmp;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected byte[] getStateInternal() {
+ return composeStateInternal(NumberFactory.makeByteArray(new int[] {a, b, c, counter}),
+ super.getStateInternal());
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected void setStateInternal(byte[] s) {
+ final byte[][] parts = splitStateInternal(s, 4 * 4);
+
+ final int[] tmp = NumberFactory.makeIntArray(parts[0]);
+ a = tmp[0];
+ b = tmp[1];
+ c = tmp[2];
+ counter = tmp[3];
+
+ super.setStateInternal(parts[1]);
+ }
+}
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/SFC64.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/SFC64.java
new file mode 100644
index 0000000..8876c58
--- /dev/null
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/SFC64.java
@@ -0,0 +1,107 @@
+/*
+ * 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 org.apache.commons.rng.core.util.NumberFactory;
+
+/**
+ * Implement the Small, Fast, Chaotic (SFC) 64-bit generator of Chris Doty-Humphrey.
+ * The original source is the PractRand test suite by the same author.
+ *
+ * <p>The state size is 256-bits; the period is a minimum of 2<sup>64</sup> and an
+ * average of approximately 2<sup>255</sup>.</p>
+ *
+ * @see <a href="http://pracrand.sourceforge.net/">PractRand</a>
+ *
+ * @since 1.3
+ */
+public class SFC64 extends LongProvider {
+ /** Size of the seed. */
+ private static final int SEED_SIZE = 3;
+
+ /** State a. */
+ private long a;
+ /** State b. */
+ private long b;
+ /** State c. */
+ private long c;
+ /** Counter. */
+ private long counter;
+
+ /**
+ * Creates an instance with the given seed.
+ *
+ * @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 SFC64(long[] seed) {
+ if (seed.length < SEED_SIZE) {
+ final long[] state = new long[SEED_SIZE];
+ fillState(state, seed);
+ setSeedInternal(state);
+ } else {
+ setSeedInternal(seed);
+ }
+ }
+
+ /**
+ * Seeds the RNG.
+ *
+ * @param seed Seed.
+ */
+ private void setSeedInternal(long[] seed) {
+ a = seed[0];
+ b = seed[1];
+ c = seed[2];
+ counter = 1L;
+ for (int i = 0; i < 18; i++) {
+ next();
+ }
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public final long next() {
+ final long tmp = a + b + counter++;
+ a = b ^ (b >>> 11);
+ b = c + (c << 3);
+ c = Long.rotateLeft(c, 24) + tmp;
+ return tmp;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected byte[] getStateInternal() {
+ return composeStateInternal(NumberFactory.makeByteArray(new long[] {a, b, c, counter}),
+ super.getStateInternal());
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected void setStateInternal(byte[] s) {
+ final byte[][] parts = splitStateInternal(s, 4 * 8);
+
+ final long[] tmp = NumberFactory.makeLongArray(parts[0]);
+ a = tmp[0];
+ b = tmp[1];
+ c = tmp[2];
+ counter = tmp[3];
+
+ super.setStateInternal(parts[1]);
+ }
+}
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 9d4b6b5..6bf0eab 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
@@ -39,6 +39,7 @@ import org.apache.commons.rng.core.source32.MultiplyWithCarry256;
import org.apache.commons.rng.core.source32.KISSRandom;
import org.apache.commons.rng.core.source32.PcgXshRr32;
import org.apache.commons.rng.core.source32.PcgXshRs32;
+import org.apache.commons.rng.core.source32.SFC32;
import org.apache.commons.rng.core.source32.PcgMcgXshRr32;
import org.apache.commons.rng.core.source32.PcgMcgXshRs32;
import org.apache.commons.rng.core.source64.SplitMix64;
@@ -53,6 +54,7 @@ import org.apache.commons.rng.core.source64.XoShiRo512Plus;
import org.apache.commons.rng.core.source64.XoShiRo512StarStar;
import org.apache.commons.rng.core.source64.MersenneTwister64;
import org.apache.commons.rng.core.source64.PcgRxsMXs64;
+import org.apache.commons.rng.core.source64.SFC64;
import org.apache.commons.rng.JumpableUniformRandomProvider;
import org.apache.commons.rng.RestorableUniformRandomProvider;
@@ -106,6 +108,7 @@ public final class ProvidersList {
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(LIST32, new SFC32(new int[] {g.nextInt(), g.nextInt()}));
// ... add more here.
// "long"-based RNGs.
@@ -122,6 +125,7 @@ public final class ProvidersList {
add(LIST64, new XoShiRo512Plus(new long[] {g.nextLong(), g.nextLong(), g.nextLong(), g.nextLong()}));
add(LIST64, new XoShiRo512StarStar(new long[] {g.nextLong(), g.nextLong(), g.nextLong(), g.nextLong()}));
add(LIST64, new PcgRxsMXs64(new long[] {g.nextLong()}));
+ add(LIST64, new SFC64(new long[] {g.nextLong(), g.nextLong()}));
// ... add more here.
// Do not modify the remaining statements.
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/SFC32Test.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/SFC32Test.java
new file mode 100644
index 0000000..70c9552
--- /dev/null
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/SFC32Test.java
@@ -0,0 +1,46 @@
+/*
+ * 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 SFC32Test {
+ @Test
+ public void testReferenceCode() {
+ /*
+ * Tested with respect to PractRand::RNGs::Raw::sfc32 of the C++ implementation (v0.94).
+ * See : http://pracrand.sourceforge.net/
+ */
+ final int[] expectedSequence = {
+ 0x89b5c414, 0x7ee57639, 0xdbe18f7b, 0x94aa0162,
+ 0xa22bff0a, 0x21c91fb8, 0x2c6fd6fe, 0xcda90d13,
+ 0x019684ca, 0xe5b400c0, 0x459d8590, 0x3aec0a1e,
+ 0x254dac77, 0xbe10ae80, 0x9ac27819, 0xd17d10c6,
+ 0x71a69026, 0x4bb2bdda, 0x70853646, 0xda28f272,
+ 0x879200d9, 0x8c2f8b5b, 0x8a87cb78, 0x27ffdced,
+ 0x988a2b7b, 0xf220ef9b, 0x13b8984f, 0x345d1732,
+ 0x8f5bc6fc, 0x092b09ff, 0x046bd2b0, 0xa5a99fc5,
+ 0x19400604, 0xb76e7394, 0x037addd5, 0xe916ed79,
+ 0x94f10dc6, 0xf2ecb45e, 0x69834355, 0xb814aeb2,
+ };
+ RandomAssert.assertEquals(expectedSequence, new SFC32(new int[] {
+ 0xbb3c4104, 0x02294965, 0xda1ce2a9
+ }));
+ }
+}
diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/SFC64Test.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/SFC64Test.java
new file mode 100644
index 0000000..b2ed395
--- /dev/null
+++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/SFC64Test.java
@@ -0,0 +1,46 @@
+/*
+ * 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 org.apache.commons.rng.core.RandomAssert;
+import org.junit.Test;
+
+public class SFC64Test {
+ @Test
+ public void testReferenceCode() {
+ /*
+ * Tested with respect to PractRand::RNGs::Raw::sfc64 of the C++ implementation (v0.94).
+ * See : http://pracrand.sourceforge.net/
+ */
+ final long[] expectedSequence = {
+ 0x383be11f844db7f4L, 0x563e7e24056ad886L, 0x959e56afde1c3f72L, 0x7924b83a8ac40b01L,
+ 0xe3096acc85876ae6L, 0x9932c32968faf17eL, 0x5df8e164496c717bL, 0x443e63b0f0636d11L,
+ 0xa0c1255bd56fb4ceL, 0xe9b12d67fbae4394L, 0x87a6b8f68968124bL, 0xe7a29a2c9eb466b6L,
+ 0xcfbcb67cac7ffb22L, 0x9a77f8d8860be8e5L, 0x51c287e3d450bf11L, 0x9518d0a2cd3f16a3L,
+ 0x36fdfd2044cbbb67L, 0x94d6e5b7e50ed797L, 0x01c80459dcc9ba5eL, 0x913aa13874b1da2aL,
+ 0x136f9eb31f816b8dL, 0xbb68f2aba658e9f5L, 0x455f38462bb2e598L, 0x216693ead3d4036dL,
+ 0x2e697d6093522eeeL, 0x8aa3e5e922c68cecL, 0x55f38b99e6e9fadcL, 0xc3b18937baf48d2fL,
+ 0xd3a84a0f0781ef03L, 0x0374b8766ea7b9a7L, 0x354736eb92044fc2L, 0x7e78cca53d9bb584L,
+ 0x6b44e298f16ca140L, 0xf1c7b84c51d8b1d8L, 0x0bee55dd0ea4439dL, 0xd9a26515c0a88471L,
+ 0xda4c3174cafc57f8L, 0x6193f4b96362eb4bL, 0x207e9a94b58041afL, 0x5451bd65c481d8fcL,
+ };
+ RandomAssert.assertEquals(expectedSequence, new SFC64(new long[] {
+ 0x012de1babb3c4104L, 0xc8161b4202294965L, 0xb5ad4eceda1ce2a9L
+ }));
+ }
+}
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 b47cb31..d435f43 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
@@ -93,6 +93,8 @@ public abstract class BaselineSources {
"PCG_MCG_XSH_RR_32",
"PCG_MCG_XSH_RS_32",
"MSWS",
+ "SFC_32",
+ "SFC_64",
})
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 449a4de..83fb9c4 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
@@ -71,6 +71,8 @@ public class RandomSourceValues {
"PCG_MCG_XSH_RR_32",
"PCG_MCG_XSH_RS_32",
"MSWS",
+ "SFC_32",
+ "SFC_64",
})
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 f9c260e..1c104f3 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
@@ -434,7 +434,23 @@ public enum RandomSource {
* <li>Native seed size: 3.</li>
* </ul>
*/
- MSWS(ProviderBuilder.RandomSourceInternal.MSWS);
+ MSWS(ProviderBuilder.RandomSourceInternal.MSWS),
+ /**
+ * Source of randomness is {@link org.apache.commons.rng.core.source32.SFC32}.
+ * <ul>
+ * <li>Native seed type: {@code int[]}.</li>
+ * <li>Native seed size: 3.</li>
+ * </ul>
+ */
+ SFC_32(ProviderBuilder.RandomSourceInternal.SFC_32),
+ /**
+ * Source of randomness is {@link org.apache.commons.rng.core.source64.SFC64}.
+ * <ul>
+ * <li>Native seed type: {@code long[]}.</li>
+ * <li>Native seed size: 3.</li>
+ * </ul>
+ */
+ SFC_64(ProviderBuilder.RandomSourceInternal.SFC_64);
/** 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 00e6524..7417cbd 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
@@ -42,6 +42,7 @@ import org.apache.commons.rng.core.source32.PcgXshRr32;
import org.apache.commons.rng.core.source32.PcgXshRs32;
import org.apache.commons.rng.core.source32.PcgMcgXshRr32;
import org.apache.commons.rng.core.source32.PcgMcgXshRs32;
+import org.apache.commons.rng.core.source32.SFC32;
import org.apache.commons.rng.core.source64.SplitMix64;
import org.apache.commons.rng.core.source64.XorShift1024Star;
import org.apache.commons.rng.core.source64.XorShift1024StarPhi;
@@ -54,6 +55,7 @@ import org.apache.commons.rng.core.source64.XoShiRo256StarStar;
import org.apache.commons.rng.core.source64.XoShiRo512Plus;
import org.apache.commons.rng.core.source64.XoShiRo512StarStar;
import org.apache.commons.rng.core.source64.PcgRxsMXs64;
+import org.apache.commons.rng.core.source64.SFC64;
/**
* RNG builder.
@@ -284,7 +286,15 @@ public final class ProviderBuilder {
final long weylState = seed;
return new long[] {state, weylState, increment};
}
- };
+ },
+ /** Source of randomness is {@link SFC32}. */
+ SFC_32(SFC32.class,
+ 3,
+ NativeSeedType.INT_ARRAY),
+ /** Source of randomness is {@link SFC64}. */
+ SFC_64(SFC64.class,
+ 3,
+ NativeSeedType.LONG_ARRAY);
/** Source type. */
private final Class<? extends UniformRandomProvider> rng;
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 698b8c9..3cc655d 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
@@ -63,6 +63,7 @@ public final class ProvidersList {
// 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(LIST32, RandomSource.SFC_32, new int[] {-23574234, 7654343});
// ... add more here.
// "long"-based RNGs.
@@ -79,6 +80,7 @@ public final class ProvidersList {
add(LIST64, RandomSource.XO_SHI_RO_512_PLUS, new long[] {89932L, -545669L, 4564689L});
add(LIST64, RandomSource.XO_SHI_RO_512_SS, new long[] {123L, -654654L, 45646789L});
add(LIST64, RandomSource.PCG_RXS_M_XS_64, new long[] {42088L, 69271L});
+ add(LIST64, RandomSource.SFC_64, new long[] {-2357423478979842L, 76543434515L});
// ... add more here.
// Do not modify the remaining statements.