7 ms·
PCG, a Family of Better Random Number Generators
- nkurz 10y agoAlthough 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.pdf 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 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-then-theres.html 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_family_of_better_random_number_generators/ 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/random123sc11.pdf 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 https://github.com/johnsalmon/boost-random123.
- pbsd 10y agoThere'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 https://eprint.iacr.org/2016/299.
- tptacek 10y agoWhat 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!