From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "Stephen J. Turnbull" Newsgroups: gmane.emacs.devel Subject: random doesn't feel very random Date: Fri, 24 Aug 2012 16:03:41 +0900 Message-ID: <87ipc8vkj6.fsf@uwakimon.sk.tsukuba.ac.jp> References: <876288yh72.fsf@kanis.fr> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 X-Trace: ger.gmane.org 1345791841 15159 80.91.229.3 (24 Aug 2012 07:04:01 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 24 Aug 2012 07:04:01 +0000 (UTC) Cc: emacs devel To: Ivan Kanis Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Aug 24 09:04:02 2012 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1T4nw0-0000rv-VR for ged-emacs-devel@m.gmane.org; Fri, 24 Aug 2012 09:04:01 +0200 Original-Received: from localhost ([::1]:49763 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1T4nvz-0007XN-5B for ged-emacs-devel@m.gmane.org; Fri, 24 Aug 2012 03:03:59 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:50273) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1T4nvr-0007X4-Ej for emacs-devel@gnu.org; Fri, 24 Aug 2012 03:03:57 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1T4nvq-0002ol-2q for emacs-devel@gnu.org; Fri, 24 Aug 2012 03:03:51 -0400 Original-Received: from mgmt2.sk.tsukuba.ac.jp ([130.158.97.224]:60150) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1T4nvp-0002js-JA for emacs-devel@gnu.org; Fri, 24 Aug 2012 03:03:50 -0400 Original-Received: from uwakimon.sk.tsukuba.ac.jp (uwakimon.sk.tsukuba.ac.jp [130.158.99.156]) by mgmt2.sk.tsukuba.ac.jp (Postfix) with ESMTP id 52A93970888; Fri, 24 Aug 2012 16:03:42 +0900 (JST) Original-Received: by uwakimon.sk.tsukuba.ac.jp (Postfix, from userid 1000) id 0F58E12081B; Fri, 24 Aug 2012 16:03:42 +0900 (JST) In-Reply-To: <876288yh72.fsf@kanis.fr> X-Mailer: VM 8.0.12-devo-585 under 21.5 (beta32) "habanero" b0d40183ac79 XEmacs Lucid (x86_64-unknown-linux) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 130.158.97.224 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:152790 Archived-At: Ivan Kanis writes: > I am using random for generating music play list. I have found that it > is not random enough. It keeps playing the same tracks. What do you mean by that? I have two somewhat different situations where there are plausible hypotheses besides "random is broken". What seems most likely is that it always plays *the same tracks in the same order*. You may have made a programming error or it may be that the pseudo-random number generator always starts from the same seed (this is useful so that a uniformly distributed sequence can be replicated if necessary -- obviously this is bad if you are using randomness as a security measure, though). This is the case for GNU random(3), which always uses the seed 1. To avoid this behavior, use `(random t)' for the first call to `random'. This uses time and some other environmental information to set the seed. It's not cryptographically strong, so a sufficiently smart cracker can probably predict what you're listening to. I hope your life doesn't depend on the secrecy of your playlist, though. :-) If it always plays tracks from the same subset of your collection, but in different orders, you may have made a programming error. > Yes I am just talking about "feeling" here. I don't know how to prove > that random does not work. Is it even possible? Sure. Analyze the code. You won't find it in Emacs, though, on most systems it uses the system random number generator, usually random(3) it looks like. On a GNU system this is a nonlinear additive feedback PRNG. If you want to prove it without knowing the algorithm, that's a lot more difficult. The basic techniques are in D. Knuth's The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. The state of the art has advanced since then, but if you can detect non-randomness with your flesh-and-blood ears, Knuth's tests will be enough. > On a side note are we using /dev/random? No, and that shouldn't be done for a system RNG. Period. It's (a) expensive (system call), (b) can block (since it depends on the dynamic environment), and (c) dangerous (it depletes your entropy pool which can slow or cripple security applications that really need it). Even using /dev/urandom to generate the seed would be overkill in almost all applications, and I wouldn't trust anybody in Emacs to write code for an application that needs that level of randomness. (That doesn't mean there are no such experts among Emacs developers, it just means I haven't seen anybody display appropriate credentials on emacs-devel. It's a *very* specialized field.)