5 ms·
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
by SethTro 6y ago
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 https://www.youtube.com/watch?v=45Oet5qjlms&t=2s
and this matrix breaks it down well
https://www.pcg-random.org/index.html https://www.pcg-random.org/index.html
- Sharlin 6y agoLCG? 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.
- klodolph 6y agoI 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
- loeg 6y agopcg64_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-practrand.html https://www.pcg-random.org/posts/128-bit-mcg-passes-practran...
- lifthrasiir 6y agoI'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.
- klodolph 6y agoYeah, 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.
- loeg 6y agoSure; to be very clear, it’s 128-bit state, 64-bit range LCGs which have great properties.
- loeg 6y agoYes, 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-standard.html 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.
- Sharlin 6y agoThanks, interesting!
- gilgoomesh 6y agoThe author of the paper is the author of Xoroshiro: https://en.wikipedia.org/wiki/Xoroshiro128%2B https://en.wikipedia.org/wiki/Xoroshiro128%2B It is certainly the algorithm the author thinks we should use.