Hacker News Reader

Comment by SethTro | Hacker News Reader

PCG and LCG (permuted/linear congruential generator) seem much stronger. This is one of my favorite presentations on the subject https://www.youtube.com/watch?v=45Oet5qjlms&t=2s

and this matrix breaks it down well https://www.pcg-random.org/index.html

View on HN

LCG? Really? Mersenne Twister originally became the cool kid because LCG's are so bad. Well, at least your standard issue `rand(3)` implementations tend(ed) to be.

Yes, 128-bit LCGs with well-chosen constant(s) are fast as hell and pass all statistical tests (you don't even need the addition factor, a good multiplier works too ("MCG")):

https://www.pcg-random.org/posts/does-it-beat-the-minimal-st...

The rand(3)s were crap because they were ~32-bit LCGs with a ~32-bit output size. You need 96-128 bits of state for a 32-64 bit output LCG.

Thanks, interesting!

I think the comment mentions LCG because it’s the basis for PCG, not because you should be using an LGC by itself.

PCG = LGC + permutation

pcg64_fast is a plain MCG (which are a subset of LCGs), and 128-bit MCGs have perfectly good statistical properties:

https://www.pcg-random.org/posts/128-bit-mcg-passes-practran...

I'm less sure about the terminology, but shouldn't we distinguish truncated LCGs from untruncated (plain) LCGs? It is clear that untruncated LCGs have very predictable lower bits by the definition and don't have "perfectly good statistical properties" by its own (it would have been fine if untruncated LCGs weren't wildly popular though). One of PCG's biggest contributions to me is a distinct name given to LCG plus tampering so that we can avoid the ambiguous "LCG" label.

Yeah, I’d think if I had to sit down and write a definition for LCG, it would just be X_(n+1) = (a X_n + c) mod m. Since we’ve discovered “high bits good, low bits bad”, we can create generators that are based on LCGs but either throw away the low bits or mix them in. I don’t know if I’d call them LCGs, though.

Sure; to be very clear, it’s 128-bit state, 64-bit range LCGs which have great properties.

The author of the paper is the author of Xoroshiro:

https://en.wikipedia.org/wiki/Xoroshiro128%2B

It is certainly the algorithm the author thinks we should use.

Reply on news.ycombinator.com