well, I already read about this low-order bit stuff, but I'm not mathematician enough to understand why.
And my doubt is not easily for me to describe in English, so with a little help of my school mathematics:
If I have a big random sample survey of "real randomly drawn numbers" then all numbers n ∈ G ={0, 1, 2,...RAND-MAX } have the same chance
P to be drawn
P(n)=
P(m) ∀ n,m ∈ G
=> all fractions of any n devided by any x ∈ Z, x << RAND-MAX ("much less than" RAND-MAX), are equally distributed:
e.g. all odd and even numbers (nx, nx+1) ∈ G ={0, 1, 2,...RAND-MAX } are equally distributed ( <=> n%2),
all numbers (nx, nx+1, nx+2) ∈ G ={0, 1, 2,...RAND-MAX } are equally distributed( <=> n%3)
and so on.
(edited)
Only if the random sample survey was not randomly taken (e.g. by a bad RNG) then also the modulo function has no randomly distribution, too.
So have a good RNG and you will get a good rand()%x subset.
By the way, as I have been told, the Kernighan and Ritchie RNG is called a "linear congruence generator" which indeed seems to have issues
http://de.wikipedia.org/wiki/Kongruenzg ... zgenerator
http://en.wikipedia.org/wiki/Linear_con ... _generator.
Wikipedia wrote:LCGs are fast and require minimal memory (typically 32 or 64 bits) to retain state. This makes them valuable for simulating multiple independent streams.
(picture: Hyperplanes of a linear congruential generator in three dimensions)
LCGs should not be used for applications where high-quality randomness is critical. For example, it is not suitable for a Monte Carlo simulation because of the serial correlation (among other things). They should also not be used for cryptographic applications; see cryptographically secure pseudo-random number generator for more suitable generators. If a linear congruential generator is seeded with a character and then iterated once, the result is a simple classical cipher called an affine cipher; this cipher is easily broken by standard frequency analysis.
LCGs tend to exhibit some severe defects. For instance, if an LCG is used to choose points in an n-dimensional space, the points will lie on, at most, m1/n hyperplanes (Marsaglia's Theorem, developed by George Marsaglia). This is due to serial correlation between successive values of the sequence Xn. The spectral test, which is a simple test of an LCG's quality, is based on this fact.
A further problem of LCGs is that the lower-order bits of the generated sequence have a far shorter period than the sequence as a whole if m is set to a power of 2. In general, the nth least significant digit in the base b representation of the output sequence, where bk = m for some integer k, repeats with at most period bn.
Nevertheless, LCGs may be a good option. For instance, in an embedded system, the amount of memory available is often severely limited. Similarly, in an environment such as a video game console taking a small number of high-order bits of an LCG may well suffice. The low-order bits of LCGs when m is a power of 2 should never be relied on for any degree of randomness whatsoever. Indeed, simply substituting 2n for the modulus term reveals that the low order bits go through very short cycles. In particular, any full-cycle LCG when m is a power of 2 will produce alternately odd and even results.
But anyway, it obviously seems to be relatively quite better than Lego rand(). My program only should show the Lego rand() issue, it should not claim that the Kernighan and Ritchie thing was the "best RNG ever".
But: If I once will manage to write a Monte Carlo simulation I will need to have a better RNG and will surely substitute the Kernighan and Ritchie thing by this even better one.
