understanding random number generation in fast-check

[skybrian]

It looks to me like fast-check uses jump() between runs to ensure each run is independent, but elsewhere it just uses clone(). Wouldn’t this result in correlation between arbitraries within the same run? For example, suppose you create two streams, one after the other?

I’m wondering if the random number generator should have a fork() operation that creates independent child streams. It seems like initializing the seeds of the child RNG with random numbers generated by the parent might work?

For background, here’s an article about the issues generating random numbers for games:

A primer for repeatable random numbers.

This paper is about a technique used for making parallel random number generators on GPU’s by using counters and hash functions:

Parallel Random Numbers: As Easy as 1, 2, 3 (PDF)

Edit: I tried it and it does seem to be pretty non-random. See #5054

[skybrian]

After chasing some references, I found out how JAX does it:

JAX PRNG Design

They advocate splittable RNGs, and here's the paper for that (from 2013):

Splittable Pseudorandom Number Generators using Cryptographic Hashing (PDF)

The first author is Koen Claessen, who is also the first author of the QuickCheck paper. And they describe in the paper how a similar bug happened in QuickCheck:

The reason for this surprising behaviour is a previously unknown flaw in the standard Haskell pseudorandom number generator used by QUICKCHECK during testing. The PRNG should pick all combinations of numbers 0–13 for a and b, but in fact combinations where a and b are the same number are never picked. It turns out that the StdGen standard generator used in current Haskell compilers contains an ad hoc implementation of splitting. The current implementation is the source of the randomness flaw demonstrated above. The flaw requires a particular pattern of split operations to manifest and results in very strong correlation of generated numbers. In fact, when 13 in the Int14 generator is replaced by other numbers from range 1–500, the problem arises for 465 of them! Unfortunately, this pattern of splits is simple and likely to arise often in typical usage of QuickCheck. Because of this, we cannot be sure that QuickCheck properties that pass a large number of tests are true with high probability.

[dubzzz]

As you pointed out, there is currently a bug causing distinct streams of values produced during the same iteration to be quite similar (offset by N).

We used to have the same issue years ago but between distinct runs and with all arbitraries. At that time our strategy has been to come up with classical tooling around PRNG by relying on jumps. Unfortunately we missed streams (will be fixed soon, I just need to find a short window to fix and test it).

So far, the plan is to stick with jumps. It remains a usual way to make draws independent from each other's. It's a key need for the arbitraries: one arbitrary should not impact another one after the generate. In other words once created stream1 should not change stream2 while we pull values out of it. It's been highly optimized code-wise making it blazing fast at execution.

Well in short, no plan to drop jumps for this major nor the next one. But the bug will be fixed 😅