Am Sun, 22 Dec 2013 09:19:48 +0000 schrieb "Chris Cain" <clc...@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.g...@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.g...@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