From owner-freebsd-current Sun Feb 2 3:48:26 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 4876D37B401 for ; Sun, 2 Feb 2003 03:48:21 -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 85A7B43E4A for ; Sun, 2 Feb 2003 03:48:20 -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 h12BmHNt044515; Sun, 2 Feb 2003 03:48:17 -0800 (PST) (envelope-from dschultz@uclink.Berkeley.EDU) Received: (from das@localhost) by HAL9000.homeunix.com (8.12.6/8.12.5/Submit) id h12BmHBD044514; Sun, 2 Feb 2003 03:48:17 -0800 (PST) (envelope-from dschultz@uclink.Berkeley.EDU) Date: Sun, 2 Feb 2003 03:48:17 -0800 From: David Schultz To: "Andrey A. Chernov" Cc: Kris Kennaway , current@FreeBSD.ORG Subject: Re: rand() is broken Message-ID: <20030202114817.GA41041@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 : > 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. Throwing away the first 10 numbers is probably not good enough to eliminate randomness with respect to the initial seed. Knuth suggests throwing away the first 2000, but he is conservative.[1] But no amount of throwing away the initial sequence will help as long as the generator itself doesn't look very random. Specifically, rand() isn't very interesting in the lower-order bits, and it spectacularly fails nearly all of Marsaglia's randomness tests.[2] If rand() is a concern to someone, they should either find LCG parameters that produce better behavior, or research a replacement algorithm. [1] His PRNG is available from http://www-cs-faculty.stanford.edu/~knuth/programs/rng.c [2] http://stat.fsu.edu/~geo/diehard.html (you need ports/lang/f2c) To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message