legacy code retreat's triva game : the D version

[Marco Leise]

Am Sun, 22 Dec 2013 09:19:48 +0000
schrieb "Chris Cain" <clcain at uncg.edu>:

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


Am Sun, 22 Dec 2013 13:09:51 +0100
schrieb Timon Gehr <timon.gehr at gmx.ch>:

> On 12/22/2013 09:06 AM, Marco Leise wrote:
> > Am Sun, 22 Dec 2013 02:12:51 +0100
> > schrieb Timon Gehr <timon.gehr at gmx.ch>:
> >
> >> On 12/22/2013 02:09 AM, Timon Gehr wrote:
> >>>>
> >>>> The morale is that "uniform" random numbers doesn't imply that
> >>>> every value in the range will eventually be generated once!
> >>>>
> >>>
> >>> Yes it does. (The probability that some value is never generated is 0.)
> >>> The actual morale is that random number generators do not generate true
> >>> randomness, and poor random number generators may generate sequences
> >>> that do not look remotely random.
> >>
> >> 'pseudo random number generators' would be a more accurate term.
> >
> > Can you elaborate a bit?
> 
> The probability that a certain number does not occur in one round is 
> (n-1)/n.
> 
> ((n-1)/n)^k goes to 0 rather fast as k goes to infinity.
> 
> In fact, the expected number of trials until all numbers are covered is 
> ~ n log n, and the probability that the process runs significantly 
> longer is very small.
> 
> See also: http://en.wikipedia.org/wiki/Coupon_collector%27s_problem
> 
> 
> > How do you know that the Java LCG can produce every 32-bit integer once?
> 
> Typically constants are chosen such that this holds, but your code would 
> require something stronger to fail, namely, that a certain congruence 
> class does not occur. Typically pseudo random number generators are 
> chosen such that the generated sequences look close to true randomness. 
> If such a simple process can be used to reliably distinguish true 
> randomness and the pseudo random number generator, then the pseudo 
> random number generator is not very good.

Thank you two for explaining LCGs to me. That's good
information for reasoning about code. Every good (full period)
LCG is a specific permutation of the numbers [0..m). The next
time I wonder how I can iterate in random order over a list of
length n^2, I know what I'll use ;)

-- 
Marco