XorShiftRng duplicates itself when sampled

[cobbal]

Since XorShiftRng implements the Rand trait, you can obtain an XorShiftRng from any Rng. Unfortunately if the original generator also happens to be an XorShiftRng you will end up with two identical generators. Example:

extern crate rand;
use rand::{SeedableRng, Rng, XorShiftRng};

fn main() {
    // (particular seed isn't important)
    let seed : [u32; 4] = [1308092148, 22089190, 2463032955, 2172661674]; 

    let mut rng1 : XorShiftRng = SeedableRng::from_seed(seed);
    let mut rng2 : XorShiftRng = rng1.gen();

    println!("rng1 -> {:?}", rng1.gen_ascii_chars().take(20).collect::<String>());
    println!("rng2 -> {:?}", rng2.gen_ascii_chars().take(20).collect::<String>());
}

results in the duplicate outputs:

rng1 -> "LJqbGKlkLfxkeYe9Ma6a"
rng2 -> "LJqbGKlkLfxkeYe9Ma6a"

This was fairly unexpected, as I was hoping (maybe foolishly) to produce an independent Rng from the first one.

[bhickey]

Xorshift RNGs belong to a broad class of RNGs that emit part of their state unaltered. Mersenne Twister, and LCGs do the same. While it's easy to guarantee that a new RNG won't be identical to the source RNG, getting a distinct RNG with desirable characteristics is tricky.

We have a few options here:

1. Skip ahead by some large number of iterations. This is easily and efficiently done with Xorshift generators. After enough splits, the state will roll over. You could choose the skip interval at random to mitigate this problem. What we really want to avoid is using the same generator in the same context, so a low and bounded collision probability is generally fine.
2. Seed the new generation with some manipulation of input state (ex. generate two 128 bit values, xor them and use the result as a seed). This is a hack, but it'll typically work.

I'm hesitant to implement either without a proof of independence. If we switch to PCG we'll get provably independent subgenerators trivially.

[dhardy]

I'm just going to say: prefer to use a strong (cryptographic or at least non-trivially reversible PRNG) as a source (Isaac64 may be a good choice if you don't mind the large state, since it is quite fast).

Skipping ahead may work but if you use several sub-generators and many values from each, there is still a chance that the ranges used may overlap (which is why a large state size is recommended for the generators).

We worked on improving the documentation for SeedableRng::from_rng and even considered restricting sources to CryptoRng but ultimately decided against it. We will eventually replace XorShiftRng with another algorithm as the default small-fast-rng.