Date: Fri, 29 Mar 1996 20:38:17 +1100 (EST) From: michael butler <imb@scgt.oz.au> To: current@freebsd.org Subject: random .. not so .. Message-ID: <199603290938.UAA12872@asstdc.scgt.oz.au>
next in thread | raw e-mail | index | archive | help
Since the random function was discussed recently .. I spotted this .. sorry
it's a little long ..
michael
From: warwick@cs.uq.edu.au (Warwick Allison)
Newsgroups: comp.os.linux.development.system,comp.bugs.4bsd
Subject: Re: Random Number Generation with Linux (using BSD) and BSD
Date: 29 Mar 1996 02:12:03 GMT
Organization: Computer Science Dept, University of Queensland
Message-ID: <4jfgtk$d71@miso.cs.uq.edu.au>
References: <1996Mar28.154520.1@rmcs.cranfield.ac.uk>
NNTP-Posting-Host: isa.cs.uq.edu.au
X-Newsreader: NN version 6.5.0 #7 (NOV)
warner@rmcs.cranfield.ac.uk (Alistair (Joe) Warner) writes:
> BSD: state[i] = 1103515245 * state[i - 1] + 12345;
> Linux: state[i] = 1103515145 * state[i - 1] + 12345;
> ^
Ha! How amusing.
That line is utterly WRONG in BOTH implementations. The state it creates
is so incredibly UNRANDOM, that seeding is almost pointless. The following
program outputs a PBM image showing a bit in the result of successive calls
to random(), for consecutive values of srandom().
The results are TERRIBLE (for example, the 151st value returned by random()
is 0 for seed 0..14, then 1 for seed 15..30, then 0 for seed 31..46, etc.)
The reason? That stupid line above.
Appended are my previous warnings about this, which have been ignored
I presume this is because most people just don't understand the problem.
Let me tell you one consequence: In one build of NetHack, it was impossible
to get a Chaotic Priest. Why you ask? Because the alignment was chosen
based on to successive 0th bits from random() calls, and the 0th bit is
the worst of all (for some number of calls of random(), it always has the
same value, regardless of initial srandom value!!!). I have tested this
under Solaris, and I get similar abysmal errors. Changing to the BSD
value will make NO DIFFERENCE. The change I give below is of the type
required for success.
#include <stdlib.h>
#define LOOP 200
#define ITER 200
main()
{
int s=time(0);
int i,l,m,j;
int seed=0;
printf("P1\n%d %d\n",ITER,LOOP);
for (l=0; l<LOOP; l++) {
srandom(seed); seed+=1;
for (i=0; i<ITER; i++) {
int b=(random()>>8)&1; /* remove >>8 for WORSE */
printf("%d\n",b);
}
}
}
>To: bug-glibc@prep.ai.mit.edu
>cc:
>Subject: PARTIAL FIX FOR: srandom() in libc
--------
The implementation of srandom() is not good. By using a poor LCRNG for
the seeding, the whole algorithm is suffering. I realize this is the
same algorithm used in every Unix C library, but hopefully *GNU* software
doesn't have to live under known errors forever.
For example, if only the zeroth bit is used from successive calls to
random(), it will give almost identical output, regardless of the
seed. This can be verified by this simple program which generates
a PBM image of streams of random numbers from different starting seeds:
main()
{
int i,l;
int seed=0;
printf("P1\n%d %d\n",100,100);
for (l=0; l<100; l++) {
srandom(seed); seed+=1;
for (i=0; i<100; i++) {
int b=random()&1;
printf("%d\n",b);
}
}
}
Nothing can be done to change the EXTREME uniformity of the resulting
image, as the code in srandom() makes a fundamental mistake: it uses a
power of two as the modulo which is mathematically a `poor' choice.
Code I suggest is better uses the largest 31-bit prime (2^31-1), which
is a `good' choice mentioned in the literature (I can find references,
if that would be useful) - the image resulting from the above is then
very random. BTW, I discovered the flaw when I noticed my version of
NetHack was NEVER giving me a lawful priest :) [nethack, like thousands
of programs, calls srandom(time(0)) to seed the generator]
Below is a patch of __srandom(), relative to glibc-1.09. Also required
would be setting the initial value of randtbl to be that achieved by
srandom(1), as these values are now different. I see that difference
as being the only argument against using the improved randomizer.
*** stdlib/__random.c Tue Jul 19 08:02:39 1994
--- stdlib/__random.c-new Mon Feb 20 11:02:46 1995
***************
*** 179,185 ****
{
register long int i;
for (i = 1; i < rand_deg; ++i)
! state[i] = (1103515145 * state[i - 1]) + 12345;
fptr = &state[rand_sep];
rptr = &state[0];
for (i = 0; i < 10 * rand_deg; ++i)
--- 179,197 ----
{
register long int i;
for (i = 1; i < rand_deg; ++i)
! {
! /*
! * Implements the following, without overflowing 31 bits:
! *
! * state[i] = (16807 * state[i - 1]) % 2147483647;
! *
! * 2^31-1 (prime) = 2147483647 = 127773*16807+2836
! */
! long int hi = state[i-1] / 127773;
! long int lo = state[i-1] % 127773;
! long int test = 16807*lo - 2836*hi;
! state[i] = test + (test<0 ? 2147483647 : 0);
! }
fptr = &state[rand_sep];
rptr = &state[0];
for (i = 0; i < 10 * rand_deg; ++i)
Newsgroups: gnu.g++.help
Subject: Re: Random Numbers
References: <47qu5b$m4q@mozo.cc.purdue.edu> <47to1e$3fc@yuma.ACNS.ColoState.EDU>
steffend@lamar.colostate.edu (Dave Steffen) writes:
>In your code I don't see any call to a "seeding" function;
WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING
The gnu libc random()/srandom() functions have (IMO) a fundamental
flaw in their implementation (as do every implementation I've tested:
rand()/srand(), lrand48()/srand48()). The random sequences do not vary
much with the seed. This can be demonstrated with:
main()
{
int i,l;
int seed=0;
printf("P1\n%d %d\n",100,100);
for (l=0; l<100; l++) {
srandom(seed); seed+=1;
for (i=0; i<100; i++) {
int b=random()&1;
printf("%d\n",b);
}
}
}
(generates a PBM image of streams of random numbers from different
starting seeds. The result SHOULD be white noise, but it looks more
like a MacPaint fill pattern!!)
Below is a patch of __srandom(), relative to glibc-1.09. Also required
would be setting the initial value of randtbl to be that achieved by
srandom(1), as these values are now different.
(this has been reported to bug-glibc@prep.ai.mit.edu, but I've had no reply)
*** stdlib/__random.c Tue Jul 19 08:02:39 1994
--- stdlib/__random.c-new Mon Feb 20 11:02:46 1995
***************
*** 179,185 ****
{
register long int i;
for (i = 1; i < rand_deg; ++i)
! state[i] = (1103515145 * state[i - 1]) + 12345;
fptr = &state[rand_sep];
rptr = &state[0];
for (i = 0; i < 10 * rand_deg; ++i)
--- 179,197 ----
{
register long int i;
for (i = 1; i < rand_deg; ++i)
! {
! /*
! * Implements the following, without overflowing 31 bits:
! *
! * state[i] = (16807 * state[i - 1]) % 2147483647;
! *
! * 2^31-1 (prime) = 2147483647 = 127773*16807+2836
! */
! long int hi = state[i-1] / 127773;
! long int lo = state[i-1] % 127773;
! long int test = 16807*lo - 2836*hi;
! state[i] = test + (test<0 ? 2147483647 : 0);
! }
fptr = &state[rand_sep];
rptr = &state[0];
for (i = 0; i < 10 * rand_deg; ++i)
--
_-_|\ warwick@cs.uq.edu.au Linux: Say `No' to broken windows.
/ * <- Comp Sci Department, McD: http://student.uq.edu.au/~s002434/mcl.html
\_.-._/ Univ. of Queensland, POV: http://student.uq.edu.au/~s002434/pov.html
v Brisbane, Australia. ME: http://student.uq.edu.au/~s002434
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199603290938.UAA12872>