random doesn't feel very random

["Stephen J. Turnbull" <stephen@xemacs.org>]

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.)