|
>linear congruential random number generator (well known, but not very good) Relevant quotes from the paper: "But if you began reading the section with the belief that “linear congruential generators are bad” (a fairly widely-held belief amongst people who know a little about random number generation), you may have been surprised by how well they performed. We’ve seen that they are fast, fairly space efficient, and at larger sizes even make it through statistical tests that take down other purportedly better generators. And that’s without an improving step." and "Despite their flaws, LCGs have endured as one of the most widely used random- number generation schemes, with good reason. They are fast, easy to implement, and fairly space efficient. As we saw in Section 3.3, despite poor performance at small bit sizes, they continue to improve as we add bits to their state, and at larger bit sizes, they pass stringent statistical tests (provided that we discard the low-order bits), actually outperforming many more-complex generators. And in a surprise upset, they can even rival the Mersenne Twister at its principle claims to fame, long period and equidistribution." "Nevertheless, there is much room for improvement. From the empirical evidence we saw in Section 3.3 (and the much more thorough treatment of L’Ecuyer & Simard [28], who observe that LCGs are only free of birthday-test issues if n < 16p1/3, where n is the number of numbers used and p is the period), we can surmise that we may observe statistical flaws in a 128-bit LCG after reading fewer than 247 numbers (which is more than BigCrush consumes but nevertheless isn’t that many—an algorithm could plausibly use one number per nanosecond and 247 nanoseconds is less than two days)." |
Yes, yes it is.
For those just as confused as I was, replace all instances of 247 with 247