From owner-freebsd-current Sun Feb 2 16:26:50 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 6BF8137B401 for ; Sun, 2 Feb 2003 16:26:48 -0800 (PST) Received: from HAL9000.homeunix.com (12-233-57-224.client.attbi.com [12.233.57.224]) by mx1.FreeBSD.org (Postfix) with ESMTP id 53F9343F85 for ; Sun, 2 Feb 2003 16:26:42 -0800 (PST) (envelope-from dschultz@uclink.Berkeley.EDU) Received: from HAL9000.homeunix.com (localhost [127.0.0.1]) by HAL9000.homeunix.com (8.12.6/8.12.5) with ESMTP id h130QdNt046834; Sun, 2 Feb 2003 16:26:39 -0800 (PST) (envelope-from dschultz@uclink.Berkeley.EDU) Received: (from das@localhost) by HAL9000.homeunix.com (8.12.6/8.12.5/Submit) id h130QdH1046833; Sun, 2 Feb 2003 16:26:39 -0800 (PST) (envelope-from dschultz@uclink.Berkeley.EDU) Date: Sun, 2 Feb 2003 16:26:39 -0800 From: David Schultz To: "Andrey A. Chernov" Cc: Kris Kennaway , current@FreeBSD.ORG Subject: Re: rand() is broken Message-ID: <20030203002639.GB44914@HAL9000.homeunix.com> Mail-Followup-To: "Andrey A. Chernov" , Kris Kennaway , current@FreeBSD.ORG References: <20030202070644.GA9987@rot13.obsecurity.org> <20030202090422.GA59750@nagual.pp.ru> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20030202090422.GA59750@nagual.pp.ru> 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 Thus spake Andrey A. Chernov : > On Sat, Feb 01, 2003 at 23:06:50 -0800, Kris Kennaway wrote: > > FreeBSD's rand() implementation has been broken for the past 23 > > months, since the following commit: > > > i.e. the first value returned from rand() is correlated with the seed > > given to srand(). This is a big problem unless your seed is randomly > > chosen over its entire integer range. I noticed this because awk > > exhibits the same problem, and the script seeds the generator with a > > PID. The script works fine under 4.x since the rand() implementation > > does not have this "feature". > > Yes, first value correlation is there, but old formulae have even worse > effect "The random sequences do not vary much with the seed", as source > file comments and whole discussion about old RNG bad effects shown. I.e. > for different time+PID sequence, especially increased monotonically, like > in common practice, you'l got the same random sequence with old formulae > (which can't be called "works fine" because this fine work was the main > reason for change). So, returning to old formulae is not an option. > > The real problem is not in formulae, but in srand() funclion. This simple > patch can fix first value correlation, and I plan to commit it, if we all > agree. I not find better value for NSHUFF right now, but think > that something like 10 will be enough to fight corellation completely. > Some generating picture tests needed. The correlation is still present with your patch and NSHUFF set to 10. For instance, try seeding rand() with contiguous monotonically increasing integers, and observe the four lowest-order bits. Just for the heck of it, I ran Marsaglia's tests on the rand() implementation in -CURRENT. The arc4random() implementation passed with flying colors as expected, whereas rand() seems to have some slight defects, particularly in the lowest and highest order bits. When I looked at rand()'s behavior with respect to different seeds, it failed miserably, both with and without your patch. The results are available at http://www.csua.berkeley.edu/~das/marsaglia/ I'm not necessarily advocating changing the algorithm at all, given that it's well known that many rand() implementations are not very random. But I also don't buy the argument that ``rand() should never ever change.'' If someone wants to do the work to improve the algorithm, that's fine with me. David Wagner has collected some links on randomness that might be helpful: http://www.cs.berkeley.edu/~daw/rnd/index.html To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message