From owner-freebsd-current Sat Oct 5 01:56:27 1996 Return-Path: owner-current Received: (from root@localhost) by freefall.freebsd.org (8.7.5/8.7.3) id BAA04036 for current-outgoing; Sat, 5 Oct 1996 01:56:27 -0700 (PDT) Received: from sovcom.kiae.su (sovcom.kiae.su [193.125.152.1]) by freefall.freebsd.org (8.7.5/8.7.3) with SMTP id BAA04029; Sat, 5 Oct 1996 01:56:23 -0700 (PDT) Received: by sovcom.kiae.su id AA29852 (5.65.kiae-1 ); Sat, 5 Oct 1996 11:43:56 +0300 Received: by sovcom.KIAE.su (UUMAIL/2.0); Sat, 5 Oct 96 11:43:55 +0300 Received: (from ache@localhost) by nagual.ru (8.7.6/8.7.3) id MAA00671; Sat, 5 Oct 1996 12:35:21 +0400 (MSD) Message-Id: <199610050835.MAA00671@nagual.ru> Subject: I plan to change random() for -current (was Re: rand() and random()) In-Reply-To: <199610041822.UAA03607@uriah.heep.sax.de> from "J Wunsch" at "Oct 4, 96 08:22:33 pm" To: joerg_wunsch@uriah.heep.sax.de Date: Sat, 5 Oct 1996 12:35:20 +0400 (MSD) Cc: freebsd-hackers@freebsd.org, current@freebsd.org (FreeBSD-current) From: =?KOI8-R?Q?=E1=CE=C4=D2=C5=CA_=FE=C5=D2=CE=CF=D7?= (Andrey A. Chernov) Organization: self X-Class: Fast X-Mailer: ELM [version 2.4ME+ PL28 (25)] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: owner-current@freebsd.org X-Loop: FreeBSD.org Precedence: bulk > I don't think so. But they are much better with random(). See xmine, > if you wanna get a nice example. It generates totally predictable > layouts when using rand(). Totally predictable layouts not rand() illness only but random() too. It not depends well on different initial state, producing the same sequence. I finally dig out initial posting (below). IMHO we need to change our random() as suggested. ------------------------------- cut me here! -------------------------- >From warwick@cs.uq.edu.au Fri Jul 5 21:11:08 1996 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) Status: RO 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 #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>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 ------------------------------- cut me here! -------------------------- -- Andrey A. Chernov http://www.nagual.ru/~ache/