PCG, a Family of Better Random Number Generators | Hacker News Reader

PCG, a Family of Better Random Number Generators

pcg-random.org

17 pointsantonios6 comments

Although this website gives you a taste of what the PCG family is and can do, the technical details are given in the paper, PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation. This paper is currently submitted to ACM Transactions on Mathematical Software, where it is currently under review.

http://www.pcg-random.org/pdf/toms-oneill-pcg-family-v1.02.p...

It's a fine paper, and so far as I can tell, a fine technique, but it's been "under review" for a long time now. Review can take a long time, but this is certainly on the slower side. I wrote to the author a while ago inquiring, but never heard back.

Another interesting recent approach is xoroshiro128+ by David Blackman and Sebastiano Vigna (vigna@acm.org): http://xorshift.di.unimi.it/xoroshiro128plus.c. Elsewhere, he pans PCG as not yet being peer reviewed: http://v8project.blogspot.com/2015/12/theres-mathrandom-and-....

Melissa O'Neill (author of PCG) compares it with Vigna's earlier XorShift+ in comments here: https://www.reddit.com/r/programming/comments/2xpr45/pcg_a_f.... The video is also a nice introduction if you prefer audio and pictures to text.

Personally, I'd be interested in seeing more analysis of "counter based" PRNG's that use hardware cryptographic approaches but with a reduced number of rounds: http://www.thesalmons.org/john/random123/papers/random123sc1.... AES has hardware support in modern processors, it's quite fast and passes all current tests for randomness, but (so far as I know) the approach hasn't yet received much academic attention. Salmon offers a Boost implementation here: https://github.com/johnsalmon/boost-random123.

There's a recent family of AES-based designs, explicitly exploiting AES-NI, that would make a good starting point for fast secure PRNGs: https://eprint.iacr.org/2016/299.

What is the scenario for which I need decent-but-not-cryptographically-secure random numbers at such a rate that the speed of the RNG is material to my design?

Serious question!

Simulations, including those that use Monte Carlo methods, might be one class of examples.

Procedurally-generated environments.

Salsa20/8 is something like 2 cycles per byte. That's too slow for procedurally generated environments?

Reply on news.ycombinator.com