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 2020/06/29 14:10:16 UTC
[commons-rng] branch master updated: [RNG-123] Document PCG
generators potential stream correlation
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
The following commit(s) were added to refs/heads/master by this push:
new 2ba9f52 [RNG-123] Document PCG generators potential stream correlation
2ba9f52 is described below
commit 2ba9f529c2eb8eec4083bd456c8b6af6b455118c
Author: aherbert <ah...@apache.org>
AuthorDate: Thu Jun 18 15:31:09 2020 +0100
[RNG-123] Document PCG generators potential stream correlation
Use of the 128-bit constructor may exhibit large correlations in output
of different streams. Notes have been added to the javadoc header and
the 128-bit constructors.
---
.../commons/rng/core/source32/AbstractPcg6432.java | 32 ++++++++++++++++++++++
.../commons/rng/core/source32/PcgXshRr32.java | 8 ++++++
.../commons/rng/core/source32/PcgXshRs32.java | 8 ++++++
.../commons/rng/core/source64/PcgRxsMXs64.java | 8 ++++++
4 files changed, 56 insertions(+)
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/AbstractPcg6432.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/AbstractPcg6432.java
index f499144..8ea52e7 100644
--- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/AbstractPcg6432.java
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/AbstractPcg6432.java
@@ -23,8 +23,40 @@ import org.apache.commons.rng.core.util.NumberFactory;
* family that use an internal 64-bit Linear Congruential Generator (LCG) and output 32-bits
* per cycle.
*
+ * <h2>Note: PCG generators may exhibit massive stream correlation</h2>
+ *
+ * <p>Although the seed size is 128 bits, only the first 64 are effective: in effect,
+ * two seeds that only differ by the last 64 bits may produce highly correlated sequences.
+ *
+ * <p>Due to the use of an underlying linear congruential generator (LCG) alterations
+ * to the 128 bit seed have the following effect: the first 64-bits alter the
+ * generator state; the second 64 bits, with the exception of the most significant bit,
+ * which is discarded, choose between one of two alternative LCGs
+ * where the output of the chosen LCG is the same sequence except for an additive
+ * constant determined by the seed bits. The result is that seeds that differ
+ * only in the last 64-bits will have a 50% chance of producing highly correlated
+ * output sequences.
+
+ * <p>Consider using the fixed increment variant where the 64-bit seed sets the
+ * generator state.
+ *
+ * <p>For further information see:
+ * <ul>
+ * <li>
+ * <blockquote>
+ * Durst, M.J. (1989) <i>Using Linear Congruential Generators For Parallel Random Number Generation.
+ * Section 3.1: Different additive constants in a maximum potency congruential generator</i>.
+ * 1989 Winter Simulation Conference Proceedings, Washington, DC, USA, 1989, pp. 462-466.
+ * </blockquote>
+ * </li>
+ * </ul>
+ *
* @see <a href="http://www.pcg-random.org/">
* PCG, A Family of Better Random Number Generators</a>
+ * @see <a href="https://ieeexplore.ieee.org/document/718715">Durst, M.J. (1989)
+ * Using Linear Congruential Generators For Parallel Random Number Generation</a>
+ * @see <a href="https://issues.apache.org/jira/browse/RNG-123">
+ * PCG generators may exhibit massive stream correlation</a>
* @since 1.3
*/
abstract class AbstractPcg6432 extends IntProvider {
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/PcgXshRr32.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/PcgXshRr32.java
index 0ebce0c..a697a3b 100644
--- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/PcgXshRr32.java
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/PcgXshRr32.java
@@ -23,6 +23,10 @@ package org.apache.commons.rng.core.source32;
*
* <p>State size is 128 bits and the period is 2<sup>64</sup>.</p>
*
+ * <p><strong>Note:</strong> Although the seed size is 128 bits, only the first 64 are
+ * effective: in effect, two seeds that only differ by the last 64 bits may produce
+ * highly correlated sequences.
+ *
* @see <a href="http://www.pcg-random.org/">
* PCG, A Family of Better Random Number Generators</a>
* @since 1.3
@@ -41,6 +45,10 @@ public class PcgXshRr32 extends AbstractPcg6432 {
/**
* Creates a new instance.
*
+ * <p><strong>Note:</strong> Although the seed size is 128 bits, only the first 64 are
+ * effective: in effect, two seeds that only differ by the last 64 bits may produce
+ * highly correlated sequences.
+ *
* @param seed Initial seed.
* If the length is larger than 2, only the first 2 elements will
* be used; if smaller, the remaining elements will be automatically set.
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/PcgXshRs32.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/PcgXshRs32.java
index 438fc38..e40acdd 100644
--- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/PcgXshRs32.java
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/PcgXshRs32.java
@@ -23,6 +23,10 @@ package org.apache.commons.rng.core.source32;
*
* <p>State size is 128 bits and the period is 2<sup>64</sup>.</p>
*
+ * <p><strong>Note:</strong> Although the seed size is 128 bits, only the first 64 are
+ * effective: in effect, two seeds that only differ by the last 64 bits may produce
+ * highly correlated sequences.
+ *
* @see <a href="http://www.pcg-random.org/">
* PCG, A Family of Better Random Number Generators</a>
* @since 1.3
@@ -41,6 +45,10 @@ public class PcgXshRs32 extends AbstractPcg6432 {
/**
* Creates a new instance.
*
+ * <p><strong>Note:</strong> Although the seed size is 128 bits, only the first 64 are
+ * effective: in effect, two seeds that only differ by the last 64 bits may produce
+ * highly correlated sequences.
+ *
* @param seed Initial seed.
* If the length is larger than 2, only the first 2 elements will
* be used; if smaller, the remaining elements will be automatically set.
diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/PcgRxsMXs64.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/PcgRxsMXs64.java
index e542c2c..38ce4c1 100644
--- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/PcgRxsMXs64.java
+++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/PcgRxsMXs64.java
@@ -25,6 +25,10 @@ import org.apache.commons.rng.core.util.NumberFactory;
*
* <p>State size is 128 bits and the period is 2<sup>64</sup>.</p>
*
+ * <p><strong>Note:</strong> Although the seed size is 128 bits, only the first 64 are
+ * effective: in effect, two seeds that only differ by the last 64 bits may produce
+ * highly correlated sequences.
+ *
* @see <a href="http://www.pcg-random.org/">
* PCG, A Family of Better Random Number Generators</a>
* @since 1.3
@@ -55,6 +59,10 @@ public class PcgRxsMXs64 extends LongProvider {
/**
* Creates a new instance.
*
+ * <p><strong>Note:</strong> Although the seed size is 128 bits, only the first 64 are
+ * effective: in effect, two seeds that only differ by the last 64 bits may produce
+ * highly correlated sequences.
+ *
* @param seed Initial seed.
* If the length is larger than 2, only the first 2 elements will
* be used; if smaller, the remaining elements will be automatically set.