Date: Sun, 25 Feb 2001 19:34:09 +0300 From: "Andrey A. Chernov" <ache@nagual.pp.ru> To: "Jacques A. Vidrine" <n@nectar.com>, Matt Dillon <dillon@earth.backplane.com>, Bruce Evans <bde@zeta.org.au>, Kris Kennaway <kris@obsecurity.org>, Robert Watson <rwatson@FreeBSD.org>, Nick Sayer <nsayer@FreeBSD.org>, 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> In-Reply-To: <20010225191316.A56093@nagual.pp.ru>; from ache@nagual.pp.ru on Sun, Feb 25, 2001 at 07:13:17PM %2B0300 References: <Pine.BSF.4.21.0102251920150.6561-100000@besplex.bde.org> <200102250900.f1P90Qc12868@earth.backplane.com> <20010225092416.A46959@hamlet.nectar.com> <20010225185535.A55782@nagual.pp.ru> <20010225191316.A56093@nagual.pp.ru>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20010225193409.A56351>