silentbicycle / greatest

A C testing library in 1 file. No dependencies, no dynamic allocation. ISC licensed.
ISC License
1.48k stars 108 forks source link

Incorrect shuffling due to PRNG bug #90

Closed silentbicycle closed 5 years ago

silentbicycle commented 5 years ago

While working on another project, I discovered that the current PRNG configuration is problematic. It uses a linear congruential random number generator, which has the handy property that (with proper configuration) it will draw all values in range once before repeating. The LCRNG's draws indicate which tests to run (in shuffled order).

The table of primes contains a couple small primes, particularly 11. The LCRNG needs that parameter to be relatively prime to the others, but it's possible for another parameter to be a multiple of 11, and in that case instead of the RNG having the full period (i.e., drawing every value once), it will draw a subset of the values multiple times (running some tests repeatedly, others not at all).

As which prime to use is chosen by the seed, this is fairly unlikely to occur by accident, but it's a strange failure mode that can be completely eliminated. The primes table will need to be changed, and possibly also the seed mask, so the ranges for those parameters no longer overlap.