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.)


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.

Reply via email to