Skip to content

Incorrect information about PRNG quality #168

Description

@alvoskov

The next manual part contains an incorrect information about quality of some generators:

https://github.com/boostorg/random/blob/develop/doc/generators.qbk

It is said that "The cycle length is a rough estimate of the quality of the generator", but it is incorrect at least for additive lagged Fibonacci generators with two lags. They do fail such basic uniformity checks (comparable to Kolmogorov-Smirnov or chi-square tests by importance) as some modifications of gap test or birthday spacings test. The failure of birthday spacings test for them is described in TAOCP vol. 2 (3rd edition) and also by G.Marsaglia (https://www.jstatsoft.org/article/view/v007i03) and TestU01 authors (https://doi.org/10.1145/1268776.1268777). Such kind of defects also can cause biases in Monte-Carlo simulations (https://doi.org/10.1103/PhysRevLett.69.3382, https://doi.org/10.1142/S0129183196000235).

I've managed to reproduce some of that failures. Moreover, a modification of gap test taken from gjrand can easily detect flaws even in additive lagged Fibonacci generators with huge lags (https://github.com/alvoskov/SmokeRand/blob/main/docs/results.md).

I think that these lagged Fibonacci generators should be described as flawed and unsuitable for any simulations (or may be even as "toy generators for writing TETRIS" or "don't pass basic tests for uniformity"). The same approach probably should be applied to generators with periods shorter than 2^60: basic tests for production ready PRNG uniformity require around 10^13 values anyway. The library already has some fast and descent generators such as MT19937, Taus88, MIXMAX, xoroshiro. But some other generators with relatively large period such as rand48, ecuyer1988 are also flawed.

P.S. I've noticed that the PRNG collection includes only "bithack" type generators but not stream ciphers such as AES-CTR, ChaCha, ThreeFish-CTR or LEA-CTR. They are not only much faster than LCG such as RANLUX but also very suitable for parallelism.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions