[
https://issues.apache.org/jira/browse/RNG-123?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16976497#comment-16976497
]
Alex Herbert commented on RNG-123:
----------------------------------
Hi Sebastiano, thank you for the report and demonstration code.
I agree that this is something we should add to the documentation.
>From the paper this seems to be the crux:
{noformat}
X_(n+1) = a X_n + c
"the two additive constants c and c + (a - 1) r produce the same sequence
(except for a shift modulo 2^e) for any r"
e is the power of 2 modulus for the LCG.{noformat}
Thus despite the 128-bit state the likelihood of overlapping correlated output
from any two PCG instances is equivalent to using a generator with a period of
2^64 from different starting points, i.e. the second seed argument serves to
alter the output but does not create uncorrelated output.
I am wondering if we should revise the user guide description of how to create
generators for parallel computation. The section on the
JumpableUniformRandomProvider is hidden in the examples. This issue with PCG
indicates that a sub-section titled 'Parallel Computations' would direct users
to an appropriate usage rather than creating multiple randomly seeded instances
of their favourite generator. The user guide could state that the later method
is subject to a likelihood of overlap that is related to the period of the
generator and its state properties with a note to check the Javadoc for the
generator for details.
As for the removal of the second seed argument there is a Pcg32 variant that
has a fixed increment (using the {{_oneseq}} nomeclature in the C++ source
code). We could add this to the enumeration choices for the RandomSource. This
would be in keeping with the library mission of providing Java implementations
of reference generators. In effect this states that since the second seed
argument is not adding substantial value you can create a generator without one.
> PCG generators may exhibit massive stream correlation
> -----------------------------------------------------
>
> Key: RNG-123
> URL: https://issues.apache.org/jira/browse/RNG-123
> Project: Commons RNG
> Issue Type: Bug
> Components: core
> Affects Versions: 1.3
> Reporter: Sebastiano Vigna
> Priority: Major
>
> [This is based on an issue I posted on the Rust development mailing list.]
> The documentation of the PCG generators does not state explicit that
> different seeds generate independent sequences, but the existence of a
> 128-bit seed implies somehow the idea that the whole seed is meaningful.
> The user should be made aware that the second parameter (the constant of the
> underlying LCG) is almost useless from a mathematical and statistical
> viewpoint.
> Changing constant to an LCG with power-of-two modulus and a constant like the
> one used in PCG simply adds a constant to the sequence (more precisely, there
> are two equivalence classes of constants, and in each equivalence class the
> sequences are identical, except for an additive constant).
> The minimal scrambling done by the generator usually cannot cancel this fact,
> and as a result changing the constant is equivalent to changing the initial
> state (modulo an additive constant). You can try to run this program:
>
> {noformat}
> import org.apache.commons.rng.core.source32.PcgXshRr32;
> import com.google.common.primitives.Ints;
> public class TestPCG {
> public static void main(final String[] args) {
> final long state = Long.parseLong(args[0]);
> final long c = Long.parseLong(args[1]);
> final long d = Long.parseLong(args[2]);
> if (c % 2 != d % 2) throw new IllegalArgumentException();
> final long C = c << 1 | 1;
> final long D = d << 1 | 1;
> final long r = 1314878037273365987L * ((d - c) >>> 1);
> final PcgXshRr32 rng0 = new PcgXshRr32(new long[] { state, c });
> final PcgXshRr32 rng1 = new PcgXshRr32(new long[] {
> 0xc097ef87329e28a5L *(6364136223846793005L * (state + C) + C - r
> - D) - D, d });
> for(;;) {
> final int a = rng0.nextInt();
> System.out.write(Ints.toByteArray(a), 0, 4);
> final int b = rng1.nextInt();
> System.out.write(Ints.toByteArray(b), 0, 4);
> }
> }
> }{noformat}
> You can pass any state as first argument, and any two constants as the
> following two arguments, as long as they are either both even or both odd .
> The program will set up a second initial state so that the sequences
> generated by the PRNGs using the two constants as seed are based on almost
> identical underlying LCG sequences, in spite of having arbitrary, different
> constants and different initial states. The two streams should be
> independent, but if you pipe the output in PractRand you'll get immediately
> {noformat}
> rng=RNG_stdin32, seed=unknown
> length= 4 megabytes (2^22 bytes), time= 2.1 seconds
> Test Name Raw Processed Evaluation
> BCFN(0+0,13-5,T) R=+263.2 p = 3.4e-103 FAIL !!!!!
> BCFN(0+1,13-5,T) R=+128.6 p = 1.5e-50 FAIL !!!!
> BCFN(0+2,13-6,T) R= +65.2 p = 9.2e-23 FAIL !!
> BCFN(0+3,13-6,T) R= +15.4 p = 1.0e-5 mildly suspicious
> DC6-9x1Bytes-1 R= +59.1 p = 4.2e-33 FAIL !!!
> DC6-6x2Bytes-1 R= +34.1 p = 9.0e-19 FAIL !
> DC6-5x4Bytes-1 R= +15.2 p = 7.7e-8 very suspicious
> [Low4/16]BCFN(0+1,13-6,T) R= +12.0 p = 1.5e-4 unusual
> [Low4/16]FPF-14+6/64:(4,14-8) R= +9.2 p = 1.1e-6 unusual
> [...]
> [Low8/32]FPF-14+6/4:(9,14-9) R= +27.4 p = 1.6e-17 FAIL
> [Low8/32]FPF-14+6/4:(10,14-10) R= +16.4 p = 2.5e-9 suspicious
> [Low8/32]FPF-14+6/4:all R=+283.4 p = 8.4e-255 FAIL !!!!!!
> [Low8/32]Gap-16:A R=+414.8 p = 2.4e-336 FAIL !!!!!!!
> [Low8/32]Gap-16:B R= +1736 p = 5e-1320 FAIL
> !!!!!!!!{noformat}
> You can also offset one of generator by hundred of iterations, but the
> sequences are so correlated that the result won't change. If you peek at the
> state of the two generators you'll see that their difference is constant.
> I think the reader should be made aware of the danger. If you start several
> generators of this kind the state is too small to guarantee that there will
> be no overlap. Once you get overlap, since there are in practice just two
> sequences, you will get a lot of unwanted correlation.
> There's a reason why nobody in the last decades ever considered creating
> "streams" using the constant part of an LCG, and it's that people realized
> very early that it doesn't work (see, e.g.,
> [https://ieeexplore.ieee.org/document/718715]).
>
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
