From owner-freebsd-current Tue Feb 4 5:44: 8 2003 Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 7ABB637B401 for ; Tue, 4 Feb 2003 05:44:02 -0800 (PST) Received: from flood.ping.uio.no (flood.ping.uio.no [129.240.78.31]) by mx1.FreeBSD.org (Postfix) with ESMTP id 0282643F79 for ; Tue, 4 Feb 2003 05:44:01 -0800 (PST) (envelope-from des@ofug.org) Received: by flood.ping.uio.no (Postfix, from userid 2602) id AA9B5536E; Tue, 4 Feb 2003 14:43:58 +0100 (CET) X-URL: http://www.ofug.org/~des/ X-Disclaimer: The views expressed in this message do not necessarily coincide with those of any organisation or company with which I am or have been affiliated. To: "Andrey A. Chernov" Cc: David Schultz , Kris Kennaway , current@FreeBSD.ORG Subject: Re: rand() is broken From: Dag-Erling Smorgrav Date: Tue, 04 Feb 2003 14:43:57 +0100 In-Reply-To: <20030204131748.GA92510@nagual.pp.ru> ("Andrey A. Chernov"'s message of "Tue, 4 Feb 2003 16:17:48 +0300") Message-ID: User-Agent: Gnus/5.090014 (Oort Gnus v0.14) Emacs/21.2 (i386--freebsd) References: <20030202070644.GA9987@rot13.obsecurity.org> <20030202090422.GA59750@nagual.pp.ru> <20030203002639.GB44914@HAL9000.homeunix.com> <20030203100002.GA73386@nagual.pp.ru> <20030204054020.GA2447@HAL9000.homeunix.com> <20030204094659.GA87303@nagual.pp.ru> <20030204115237.GA6483@HAL9000.homeunix.com> <20030204131006.GB92301@nagual.pp.ru> <20030204131748.GA92510@nagual.pp.ru> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Sender: owner-freebsd-current@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.ORG --=-=-= "Andrey A. Chernov" writes: > There is one bug in your patch: 0 is still illegal, so my fix required. I believe that's a feature. All linear congruence generator have a fixed point. 0 is a far better fixed point than any other because it is more "obviously unsuited" (for some values of "obviously") as a seed value. (but see below) > The next bug is that there is % RAND_MAX + 1, not % RAND_MAX. No, using modulo 0x80000000 instead of modulo 0x7fffffff breaks the algorithm. (but see below) > The next is not the bug but portability thing alowing different RAND_MAX: > you need to assign *ctx first and return it % RAND_MAX + 1 next, not > assign *ctx % RAND_MAX + 1 like you currently does. Changing RAND_MAX affects the algorithm in such a way that you should not do so without giving serious thought to revising the algorithm itself. In fact, RAND_MAX should be considered a characteristic of the algorithm rather than a parameter that regulates it. For that reason, and to make the algorithm more transparent to the reader, I've replaced RAND_MAX with 0x7fffffff in the attached patch. All that being said, adding 1 to *ctx before returning it (see patch) adresses both of your objections: a seed of 0 will not cause the LCG to get stuck, and the result of rand() will range between 0 and RAND_MAX inclusive. des@des ~/src% ./rndtest| head 2 0 1 7 1 7 f 2 5 3 f 6 a d 6 a 3 b 5 2 f 8 6 3 d 9 6 1 f 0 2 3 4 4 1 a f 3 b 5 4 2 a 6 f 0 0 6 9 5 1 7 c f 6 9 1 7 7 a 7 8 1 b 0 a c 7 a c 7 3 9 f 4 2 d 3 d 9 d 4 4 a 3 0 c f 7 6 2 5 9 2 3 7 5 b 7 7 f 9 9 b d 1 d c 5 2 b 6 7 c c 5 8 4 3 b 2 1 6 f 6 c 2 2 5 6 5 e a b b 8 e e 4 9 1 9 4 2 3 4 d b 3 5 3 a d 4 3 5 b 7 4 a c 1 2 4 e 5 d 9 0 6 6 8 b 7 f 8 8 2 6 1 c d 1 c f f 0 9 1 3 4 c 5 6 8 b 8 9 a 8 5 d b 8 8 d 7 e 7 0 c 2 c 8 0 6 5 8 f 8 9 6 0 c 9 d 4 7 0 8 5 2 c b 8 e 5 f 5 c d 1 c c b 3 8 8 f f 1 2 a 5 c f 0 5 f 2 4 e 9 0 1 1 9 2 5 f 0 0 2 2 d f b f 7 0 2 a 2 4 7 a 2 f 9 0 f 1 c 8 e 2 f c f 2 8 c d 5 7 0 f 2 b a 2 a 4 d 8 b c 4 0 4 DES -- Dag-Erling Smorgrav - des@ofug.org --=-=-= Content-Type: text/x-patch Content-Disposition: attachment; filename=rand.diff Index: lib/libc/stdlib/rand.c =================================================================== RCS file: /home/ncvs/src/lib/libc/stdlib/rand.c,v retrieving revision 1.11 diff -u -r1.11 rand.c --- lib/libc/stdlib/rand.c 2 Feb 2003 14:27:51 -0000 1.11 +++ lib/libc/stdlib/rand.c 4 Feb 2003 13:33:30 -0000 @@ -52,7 +52,7 @@ #endif /* TEST */ static int -do_rand(unsigned long *ctx) +do_rand(uint32_t *ctx) { #ifdef USE_WEAK_SEEDING /* @@ -63,21 +63,23 @@ return ((*ctx = *ctx * 1103515245 + 12345) % ((u_long)RAND_MAX + 1)); #else /* !USE_WEAK_SEEDING */ /* - * Compute x = (7^5 * x) mod (2^31 - 1) - * wihout overflowing 31 bits: - * (2^31 - 1) = 127773 * (7^5) + 2836 - * From "Random number generators: good ones are hard to find", - * Park and Miller, Communications of the ACM, vol. 31, no. 10, - * October 1988, p. 1195. + * New algorithm derived from + * The Laws of Cryptography: Pseudo-random Number Generation + * by Neal R. Wagner + * http://www.cs.utsa.edu/~wagner/laws/rng.html + * which itself is derived from work by Donald E. Knuth. + * + * This is a linear congruence generator using the equation + * + * x(n+1) = (k * x(n) + a) mod m + * + * where m is 2^31 - 1, k is 62089911 and a is 0. */ - long hi, lo, x; + uint64_t tmp; - hi = *ctx / 127773; - lo = *ctx % 127773; - x = 16807 * lo - 2836 * hi; - if (x <= 0) - x += 0x7fffffff; - return ((*ctx = x) % ((u_long)RAND_MAX + 1)); + tmp = *ctx * 62089911; + *ctx = (uint32_t)(tmp % (uint64_t)0x7fffffff + 1); + return (*ctx); #endif /* !USE_WEAK_SEEDING */ } @@ -85,7 +87,7 @@ int rand_r(unsigned int *ctx) { - u_long val = (u_long) *ctx; + uint32_t val = (uint32_t) *ctx; int r = do_rand(&val); *ctx = (unsigned int) val; @@ -93,7 +95,7 @@ } -static u_long next = 1; +static uint32_t next = 1; int rand() --=-=-=-- To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message