PCG – A Family of Better Random Number Generators

PCG – A Family of Better Random Number Generators(pcg-random.org)

13 points by Uzomidy 11 years ago | 9 comments

aidenn0 11 years ago |

The author does not indicate what sort of target the benchmarks were run on, but for comparison ChaCha20/8 which is a more modern secure PRNG compared to the arcfour that they show runs about 10Gb/s on modern hardware.

ChaCha20/20 is a more conservative choice (i.e. there are classes of attacks on ChaCha20/8 that would be infeasible against ChaCha20/20) but runs somewhere between 1/3 and 1/2 the speed of 20/8.

Uzomidy 11 years ago | |

The benchmark details are in the paper. It's a pretty ordinary Haswell PC.

trebor 11 years ago |

I'd like to see more substantiation than the guy's own site. The PCG "family" is omitted from every graph that I saw. Also, from my own testing, Mersenne Twister appears to have enough randomness for non-cryptographic purposes. I've never had particularly predictable sequences from it.

Uzomidy 11 years ago | |

The graphs of failures don't show the PCG scheme because their number of failures is zero.

The performance graphs show a whole bunch of PCG generators.

You absolutely can predict the Mersenne Twister after 624 outputs (there are several blog posts out there). The Mersenne Twister is also huge (2K of state) and some people claim that as a result it's not cache friendly.

But yes, it's a new thing, so it needs people to look at it.

pkhuong 11 years ago | |

How would you test for bad sequences? Does that method manage to flag http://en.wikipedia.org/wiki/RANDU?

Uzomidy 11 years ago |

Apparently, both the Mersenne Twister and XorShift (which seem to be two of the popular RNGs people use these days) can't pass all statistical tests. (The Mersenne Twister is pretty huge as well.)

aidenn0 11 years ago | |

Some xorshifts can and some can't; I don't think any 64-bit xorshift does.

Uzomidy 11 years ago | | |

Looking at the PCG paper, it shows that a basic XorShift generator doesn't pass statistical tests as it gets bigger. Basically, there are some tests it never passes no matter how big it gets.

But a tiny change (XorShift*) is enough to get a generator that passes empirical statistical tests.

The page about other RNGs has lots of good info about this stuff.