On Sunday, 22 December 2013 at 08:06:30 UTC, Marco Leise wrote:

Can you elaborate a bit? How do you know that the Java LCG can produce every 32-bit integer once? If that's true then the problem with the Java code was something different and I was just biased, because I was already expecting the code to fail before the fact. (Expectations can do strange things to your perception.)

## Advertising

If I may, http://en.wikipedia.org/wiki/Linear_congruential_generator Definition of an LCG: ``` Xnext = (a * Xprev + c) % m ```

`An LCG is said to have a "full period" if the length of the`

`period is m. If the period is m, we know the LCG must produce`

`every number between 0 and m because if there was even one`

`repeated number then the generator as defined above would repeat`

`the entire sequence up to that point and, thus, the period would`

`not be m, which is a contradiction.`

`According to the Hull-Dobell Theorem, an LCG will have a full`

`period iff:`

1. `c` and `m` are relatively prime. For Java, c = 11 and m = 2^48 This condition applies. 2. `(a - 1)` is divisible by all prime factors of m`

`For Java, a = 25214903917 and thus a-1 is even which means the`

`prime factors of m (just 2) do divide it.`

This condition applies. 3. `a - 1` is a multiple of 4 if `m` is a multiple of 4. For Java, m is a multiple of 4. `(a - 1)/4` is 6303725979, so it's also a multiple of 4. This condition applies as well.

`Since Java's LCG has a full period over 2^48, we know that taking`

`the top 32 bits (which is what Java does to get "better"`

`randomness) would also all be represented.`