From owner-svn-src-all@FreeBSD.ORG Tue Jul 2 16:33:38 2013 Return-Path: Delivered-To: svn-src-all@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by hub.freebsd.org (Postfix) with ESMTP id 02E5D832; Tue, 2 Jul 2013 16:33:38 +0000 (UTC) (envelope-from brde@optusnet.com.au) Received: from mail105.syd.optusnet.com.au (mail105.syd.optusnet.com.au [211.29.132.249]) by mx1.freebsd.org (Postfix) with ESMTP id BDA2E18A6; Tue, 2 Jul 2013 16:33:37 +0000 (UTC) Received: from c122-106-156-23.carlnfd1.nsw.optusnet.com.au (c122-106-156-23.carlnfd1.nsw.optusnet.com.au [122.106.156.23]) by mail105.syd.optusnet.com.au (Postfix) with ESMTPS id D026710425B7; Wed, 3 Jul 2013 02:33:30 +1000 (EST) Date: Wed, 3 Jul 2013 02:33:29 +1000 (EST) From: Bruce Evans X-X-Sender: bde@besplex.bde.org To: Andrey Chernov Subject: Re: RAND_MAX broken In-Reply-To: <51D2F571.8050108@freebsd.org> Message-ID: <20130703020550.E8632@besplex.bde.org> References: <201307012143.r61Lhemi067176@svn.freebsd.org> <20130702130818.V865@besplex.bde.org> <20130702165642.X1571@besplex.bde.org> <51D2F571.8050108@freebsd.org> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Optus-CM-Score: 0 X-Optus-CM-Analysis: v=2.0 cv=eqSHVfVX c=1 sm=1 a=kj9zAlcOel0A:10 a=PO7r1zJSAAAA:8 a=JzwRw_2MAAAA:8 a=lqUz0ovpAEAA:10 a=Aq5J0u6kN07AkTABL6YA:9 a=CjuIK1q_8ugA:10 a=ebeQFi2P/qHVC0Yw9JDJ4g==:117 Cc: svn-src-head@freebsd.org, svn-src-all@freebsd.org, "Pedro F. Giffuni" , src-committers@freebsd.org, Bruce Evans X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 02 Jul 2013 16:33:38 -0000 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