From owner-cvs-all Sun Feb 25 8:34:42 2001 Delivered-To: cvs-all@freebsd.org Received: from nagual.pp.ru (pobrecita.freebsd.ru [194.87.13.42]) by hub.freebsd.org (Postfix) with ESMTP id 32F4B37B401; Sun, 25 Feb 2001 08:34:31 -0800 (PST) (envelope-from ache@nagual.pp.ru) Received: (from ache@localhost) by nagual.pp.ru (8.11.2/8.11.2) id f1PGYBv56414; Sun, 25 Feb 2001 19:34:11 +0300 (MSK) (envelope-from ache) Date: Sun, 25 Feb 2001 19:34:09 +0300 From: "Andrey A. Chernov" To: "Jacques A. Vidrine" , Matt Dillon , Bruce Evans , Kris Kennaway , Robert Watson , Nick Sayer , cvs-committers@FreeBSD.org, cvs-all@FreeBSD.org Subject: rand.c patch for review (was: Re: cvs commit: ports/astro/xglobe/files patch-random) Message-ID: <20010225193409.A56351@nagual.pp.ru> References: <200102250900.f1P90Qc12868@earth.backplane.com> <20010225092416.A46959@hamlet.nectar.com> <20010225185535.A55782@nagual.pp.ru> <20010225191316.A56093@nagual.pp.ru> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: <20010225191316.A56093@nagual.pp.ru>; from ache@nagual.pp.ru on Sun, Feb 25, 2001 at 07:13:17PM +0300 Sender: owner-cvs-all@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG On Sun, Feb 25, 2001 at 19:13:17 +0300, Andrey A. Chernov wrote: > On Sun, Feb 25, 2001 at 18:55:36 +0300, Andrey A. Chernov wrote: > > On Sun, Feb 25, 2001 at 09:24:16 -0600, Jacques A. Vidrine wrote: > > > My conclusion is that either: > > > > > > Our implementation of `rand' loses. > > > > We can easily improve much our rand() random distribution staying inside > > the same API by using just different calculation formula, as we already do > > with random(). I plan to do it long time ago, but lost interest. I can dig > > out this formula, if someone is interested. > > We already use this formula (in different context), see > good_rand() function in stdlib/random.c Patch for review: --- rand.c.bak Thu Aug 19 19:30:29 1999 +++ rand.c Sun Feb 25 19:30:15 2001 @@ -47,7 +47,31 @@ static int do_rand(unsigned long *ctx) { +#ifdef USE_WEAK_SEEDING +/* + * Historic implementation compatibility. + * The random sequences do not vary much with the seed, + * even with overflowing. + */ 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. + */ + long hi, lo, x; + + hi = *ctx / 127773; + lo = *ctx % 127773; + x = 16807 * lo - 2836 * hi; + if (x <= 0) + x += 0x7fffffff; + return ((*ctx = x) % ((u_long)RAND_MAX + 1)); +#endif /* !USE_WEAK_SEEDING */ } -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe cvs-all" in the body of the message