3 ms·
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
by Sharlin 6y ago
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.
- 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!