Date: Wed, 3 Jul 2013 02:33:29 +1000 (EST) From: Bruce Evans <brde@optusnet.com.au> To: Andrey Chernov <ache@freebsd.org> Cc: svn-src-head@freebsd.org, svn-src-all@freebsd.org, "Pedro F. Giffuni" <pfg@freebsd.org>, src-committers@freebsd.org, Bruce Evans <brde@optusnet.com.au> Subject: Re: RAND_MAX broken Message-ID: <20130703020550.E8632@besplex.bde.org> In-Reply-To: <51D2F571.8050108@freebsd.org> References: <201307012143.r61Lhemi067176@svn.freebsd.org> <20130702130818.V865@besplex.bde.org> <20130702165642.X1571@besplex.bde.org> <51D2F571.8050108@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Tue, 2 Jul 2013, Andrey Chernov wrote: > On 02.07.2013 11:39, Bruce Evans wrote: >> The bugs are a little different than I said above. There is no overflow >> problem and no problem with invalid values being produces, since the >> algorithm from ACM is careful to do everything with 32 bit signed >> integers without causing overflow. The algorithm just doesn't produce >> values mod 2**32 as expected by all the functions. It does what it >> claims to do -- it produces values mod (2**32 - 1). The largest bug >> is that RAND_MAX is off by 1. It is specified as the largest value >> returned by rand(), but in FreeBSD rand() never returns it unless >> USE_WEAK_SEEDING is confgured. The values should be unifornly >> distributed on average beteen 0 and RAND_MAX,but that is impossible >> if RADND_MAX is never returned. From libc/stdlib/srand.c: > > Don't ever consider USE_WEAK_SEEDING defined - result is distributet > _very_ poorly and the code should be removed long time ago. > > BTW, I don't understand well fixes you suggest. Is it to define RAND_MAX > as 0x7ffffffe ? That would would be more correct. It might have compatibility problems. I checked the values returned by rand(). The ACM part works as intended, so it never returns RAND_MAX. It also never returns 0. So the distribution of values in the documented range [0, RAND_MAX] is very non-uniform. It is uniform in [1, RAND_MAX - 1]. To use this algorithm for rand(), 1 should have been subtracted, giving a range of [0, 0x7ffffffe]. In mathematical terms, the algorithm uses the (multiplicative) group of units in the field Z/(0x7fffffff.Z), but for rand() we want the values to be in the the additive group Z/(0x7ffffffe.Z). Subtracting 1 doesn't preserve the group operation but gives the right set of values. 0x7ffffffff is used because it is prime. 0x800000001, 0xffffffff and 0x100000001 are not prime, so the algorithm can't easily be modified to give the range [0, 0x7fffffff] or a 32-bit range. The most interesting prime near 2**31 or 2*32 is 2**32 - 5. Bruce
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20130703020550.E8632>