Rosetta Code

Random number generator (included): Difference between revisions

Page Discussion

Random number generator (included) (view source)

Revision as of 04:31, 16 July 2011

5 bytes added ,  12 years ago
→‎BSD rand(): n bits can contain only 2^n states whatever you do: it's the repeat length that matters
(→‎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:
[[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() canproduces cyclea cycling sequence throughof 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 throughsequence length is only <math>2^n</math> possible states. (This problem happens because the modulus <math>2^{31}</math> is not a primepower of numbertwo.) 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>
Line 102:
* 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 cycleperiod length 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.
 
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().
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/136572"