Random number generator (included): Difference between revisions

Content added Content deleted
(→‎C rand(): The perils of BSD rand(): "This is not a real coin, and these are not truly random flips." The formula of Microsoft rand().)
(→‎BSD rand(): n bits can contain only 2^n states whatever you do: it's the repeat length that matters)
Line 81: Line 81:
[[FreeBSD]] switched to a different formula, but [[NetBSD]] and [[OpenBSD]] stayed with this formula. ([http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/stdlib/rand.c?only_with_tag=MAIN NetBSD rand.c], [http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/rand.c OpenBSD rand.c])
[[FreeBSD]] switched to a different formula, but [[NetBSD]] and [[OpenBSD]] stayed with this formula. ([http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/stdlib/rand.c?only_with_tag=MAIN NetBSD rand.c], [http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/rand.c OpenBSD rand.c])


BSD rand() can cycle through only <math>2^{31}</math> possible states; this is already too short to produce good random numbers. The big problem with BSD rand() is that the low <math>n</math> bits cycle through only <math>2^n</math> possible states. (This problem happens because the modulus <math>2^{31}</math> is not a prime number.) The worst case, when <math>n = 1</math>, becomes obvious if one uses the low bit to flip a coin.
BSD rand() produces a cycling sequence of only <math>2^{31}</math> possible states; this is already too short to produce good random numbers. The big problem with BSD rand() is that the low <math>n</math> bits cycle sequence length is only <math>2^n</math>. (This problem happens because the modulus <math>2^{31}</math> is a power of two.) The worst case, when <math>n = 1</math>, becomes obvious if one uses the low bit to flip a coin.


<lang c>#include <stdio.h>
<lang c>#include <stdio.h>
Line 102: Line 102:
* At odd seconds: tails, heads, tails, heads, tails, heads, tails, heads, tails, heads.
* At odd seconds: tails, heads, tails, heads, tails, heads, tails, heads, tails, heads.


The low bit manages a uniform distribution between heads and tails, but it has a cycle of only 2 states: it can only flip a coin 2 times before it must repeat itself. Therefore it must alternate heads and tails. This is not a real coin, and these are not truly random flips.
The low bit manages a uniform distribution between heads and tails, but it has a period length of only 2: it can only flip a coin 2 times before it must repeat itself. Therefore it must alternate heads and tails. This is not a real coin, and these are not truly random flips.


In general, the low bits from BSD rand() are much less random than the high bits. This defect of BSD rand() is so famous that some programs ignore the low bits from rand().
In general, the low bits from BSD rand() are much less random than the high bits. This defect of BSD rand() is so famous that some programs ignore the low bits from rand().
Retrieved from "https://rosettacode.org/wiki/Random_number_generator_(included)"