Document dependency between streams in PCG64

[vigna]

The documentation of the PCG generators with a "stream" parameter does not state explicit that different streams generate independent sequences, but the existence of a parameter named "stream" implies somehow the idea.

The user should be made aware that the stream parameter is almost useless from a mathematical and statistical viewpoint.

Changing constant (stream) 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 cannot cancel this fact, and as a result changing the constant is basically equivalent to changing the initial state. You can try to run this program:

extern crate rand_pcg;
use rand::{Rng};

fn main() {
    let state : u128  = 0x596d84dfefec2fc76b79f81ab9f3e37b; // Original state
    let c : u128 = 0x702bdbf7bb3c0a7ac28fa16a64abf95; // Original increment parameter (must be odd)
    let c_ : u128 = c << 1 | 1; // Actual increment
    let d_ : u128 = 0xba6724c0f47893162ee214efcc33da13; // Any other actual increment (must be congruent to 3 mod 8)

    let mut r : u128 = 68263968060690495638840298501726217073;
    r = r.wrapping_mul((d_ - c_) / 4);

    let mut r0 = rand_pcg::Pcg64::new(state.wrapping_sub(c_), c);
    let mut r1 = rand_pcg::Pcg64::new(state.wrapping_sub(d_).wrapping_sub(r), d_ >> 1);

    loop {
        let x: u64 = r0.gen();
        let y: u64 = r1.gen();
        println!("0x{:x}", x);
        println!("0x{:x}", y);
    }
}

You can change state as you like, and the two constants c and d_ as you like. The program will set up two initial states so that the sequences generated by the two PRNGs are based on almost identical underlying LCG sequences, in spite of having arbitrary constants (stream parameters). I don't know how to write in binary in Rust, but I passed the output through this simple C program

 #include <stdio.h>
 #include <stdlib.h>
 #include <stdint.h>

 int main() {
         char s[100];

         for(;;) {
                 gets(s);
                 const uint64_t x = strtoull(s, NULL, 0);
                 fwrite(&x, sizeof x, 1, stdout);
        }
}

and then through PractRand. If you comment one of the println!, everything is fine. If you interleave the two generators:

rng=RNG_stdin64, seed=unknown
length= 16 megabytes (2^24 bytes), time= 3.3 seconds
  Test Name                         Raw       Processed     Evaluation
  BCFN(0+0,13-4,T)                  R=+472.4  p =  2.4e-206   FAIL !!!!!!
  BCFN(0+1,13-4,T)                  R=+663.5  p =  8.2e-290   FAIL !!!!!!
  BCFN(0+2,13-5,T)                  R=+367.3  p =  6.0e-144   FAIL !!!!!
  BCFN(0+3,13-5,T)                  R=+564.4  p =  4.1e-221   FAIL !!!!!!
  DC6-9x1Bytes-1                    R= +64.4  p =  5.7e-37    FAIL !!!
  DC6-6x2Bytes-1                    R= +98.4  p =  1.8e-56    FAIL !!!!
  DC6-5x4Bytes-1                    R= +45.4  p =  1.3e-27    FAIL !!
  [Low4/16]BCFN(0+0,13-5,T)         R= +81.3  p =  5.3e-32    FAIL !!!
  [Low4/16]BCFN(0+1,13-5,T)         R=+144.4  p =  1.0e-56    FAIL !!!!
  [Low4/16]BCFN(0+2,13-6,T)         R= +14.8  p =  1.7e-5   mildly suspicious
  [Low4/16]DC6-9x1Bytes-1           R= +16.0  p =  8.1e-9    VERY SUSPICIOUS
  [Low4/16]DC6-6x2Bytes-1           R= +32.7  p =  5.2e-18    FAIL !
  [Low4/16]DC6-5x4Bytes-1           R= +45.6  p =  1.7e-22    FAIL !!
  [Low4/16]FPF-14+6/4:(0,14-1)      R=+128.3  p =  1.9e-113   FAIL !!!!!
  [Low4/16]FPF-14+6/4:(1,14-2)      R=+126.7  p =  1.4e-110   FAIL !!!!!
  [Low4/16]FPF-14+6/4:(2,14-2)      R= +79.0  p =  7.3e-69    FAIL !!!!
  [Low4/16]FPF-14+6/4:(3,14-3)      R= +17.5  p =  4.2e-15    FAIL
  [Low4/16]FPF-14+6/4:(4,14-4)      R=  +9.3  p =  1.4e-7   mildly suspicious
  [Low4/16]FPF-14+6/4:all           R=+179.8  p =  3.3e-168   FAIL !!!!!
  ...and 849 test result(s) without anomalies

You can also offset one of generator by hundred of iterations, but the sequences are so correlated that the result won't change.

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.

[dhardy]

Good points; I made some changes to the book in this regard but the API documentation warrants review too.

A secondary point is that on 32-bit platforms we currently use PCG32 with streams in SmallRng source, which isn't ideal. (However, we recommend StdRng or thread_rng for most usage, both of which use cryptographic generators, so this won't affect most users.)

[vigna]

That's dangerous. There's a reason why nobody in the last decades ever considered (OK, except Melissa O'Neill) 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).

[vks]

I wonder about the best way to fix this. Maybe remove the stream parameter in a breaking release? (Deprecating is tricky, because we would have to deprecate {Lcg128Xsl64, Lcg64Xsh32}::new, and we likely want to change from_seed too, which is a breaking change in any case.) Unfortunately, this would make the seed of Lcg64Xsh32 only 64 bits, which is a bit too small.

[dhardy]

@vks I don't see any point hacking PCG to "fix" this. Sure, PCG has single-stream variants, but since one of the biggest reasons to use non-crypto RNGs is to allow multiple generators without hitting memory usage/bandwidth/cache too hard, a 64-bit generator without streams is not so useful. I'm also a bit concerned about this limitation (which is to do with the state, not the stream).

Therefore we should consider replacing PCG for use in SmallRng (but leave rand_pcg as just another PRNG crate, with some additional warnings). But lets move this discussion to a new thread: #910.