Hacker News Reader

Comment by Veedrac | Hacker News Reader

One of the most important things that came out of The PCG Paper[1] is that tests are stronger as you reduce the number of state bits, and measuring this continuum is much more powerful than a single test. (see Figure 7)

It seems to me that any new non-cryptographic PRNG should be required to test itself in this manner, or else provide a very good excuse.

[1] http://www.pcg-random.org/paper.html

View on HN

Addendum: For what it's worth, it seems some people aren't fond of Diehard any more. To quote Chris Doty-Humphrey, the author of PractRand:

> In empirical testing, a classic is the Diehard program by Marsaglia. That program is badly outdated today and should not be used anymore, but it was, so far as I know, the first real standardized battery of such tests.

More information is available on their website: http://pracrand.sourceforge.net/PractRand.txt.

From what I gather, decent PRNG tests today are

- L'Ecuyer's TestU01 (with SmallCrush, Crush, BigCrush), and

- Doty-Humphrey's pracrand with its PractRand suite

PCG seems to be designed by intuition and experimentation, with practically no theory in its support. I'm not saying it's bad, and I certainly see some potential merit in the idea that a PRNG passing tests with fewer bits is likely more effective than one that needs more state.

The problem is that these test suites are not very comprehensive and while they're OK for discerning an obviously broken RNG, they're not good to vouch for an RNG in general. That is to say, it is fairly easy to write an RNG that passes these test suites despite having some very predictable and easily detectable patterns that you'd find if only you wrote a test that looks for that particular pattern. Kinda like these suites have hyperplane tests to detect LCGs.

There's an old saying about anyone being smart enough to invent crypto they are not smart enough to break themselves. As far as designing RNGs goes, doing one against existing test suites is pretty low bar. I think we can afford a little more theory backing non-cryptographic PRNGs too.

I wouldn't give these test suites so much credit; they're tools for detecting known flaws or broken implementations. That's all.

While the PCG paper does not contain such an impressive number of mathematical formula's that makes me instantly want to skip pages, I would not say it has 'practically no theory in its support'.

For the theory around periods, distribution and jumping it can just refer to these properties for LCG's, which are very well studied.

Testing an RNG design against the statistical test suites TestU01 and PractRand seems on first intuition the be the wrong way to go about it. First you should have a theory behind the RNG, and only then test it.

And to me it seems PCG does just that. The various output functions are carefully designed. Which bits are the best and which are the weakest for an LCG? The worst bits are dismissed. How can the best bits be used to pick permutations of the remaining bits? The output functions are well designed, but you will have to watch the video or look at the C++ source to see the theory behind them.

Then just about all known tests and theory to differentiate between true randomness and the results of an RNG are applied. Which are handily packed into test suites. That is the way to look at these tests. Not some sort of specific, arbitrarily chosen test. This is not the situation of Javascript engines that may get optimized to much for some arbitrary benchmark.

And those test where run against severely weakened versions of PCG, just to be sure the tests don't accidentally pass.

But you have a good point: designing solely against test suites is not a good idea. A result are Xorshift128+ and Xoroshiro128+. Even with some theory behind it, they are the result of varying constants until they do not fail any test on BigCrush too consistently. It may even sometimes pass, and that is what is claimed on for example Wikipedia. But along comes another test suite, PractRand, and it fails within a second of testing. It is optimized for BigCrush, but not really statistically good.

What would you recommend that isn't far worse, though? At least the PCG family tries; throwing that away can't give you better results. There's a good reason the PCG generators have remained robust against new tests, and why the well regarded competitors like the Mersenne Twister and Xoroshiro128+ have not.

Unless the competition is actually using rigorous mathematics to talk about their statistical quality, and as far as I can find they are simply not[1], being empirically better is the only thing to argue about! Thus if O'Neil's approach finds weaknesses in the competitor's tested generators earlier[2], it's a stronger test.

Even from the angle of unknown, theoretical attacks, competitors almost always build on trivially invertible functions, so you cannot expect them to be robust against generalized tests. The inverse transformation is always weak, so if this is trivial they cannot be robust against general classes of correlations.

Unless you can actually show a (useful) non-cryptographic RNG that makes good justifications for its strength in formal terms, which I doubt you can, you're basically left with the fact that the PCG family is the only robustly vetted family in practice.

If that isn't good enough for you, there's always ISAAC.

[1] https://cs.stackexchange.com/questions/50059/why-is-the-mers...

[2] http://www.pcg-random.org/posts/visualizing-the-heart-of-som...

Reply on news.ycombinator.com