legacy code retreat's triva game : the D version

[Chris Cain]

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.