Is the iPod Shuffle Mode Really Random?

I don't have an iPod and have never used one, but the obvious answer is "No." I've recently heard this discussed on the Network Security Podcast and on NPR Weekend Edition. What's random on a digital device? A good example is Stephen Park and Keith Miller's minimal standard generator (see their 10/88 CACM article). This is (perhaps) the same generator, being based on a linear-congruential generator from Dr. Park's simulation course at William & Mary, spring 1986:

double Random(long *seed) {
  const int a     = 16807;       /* multiplier */
  const int m     = 2147483647;  /* modulus */
  const int alpha = 127773;      /* m div a */
  const int beta  = 2836;        /* m mod a */

  int    lo, hi, test;

  assert(*seed > 0);

  hi = *seed / alpha;
  lo = *seed - alpha * hi;
  test = a * lo - beta * hi;
  if (test < 1)
      *seed = test + m;
  else
     *seed = test;
  return ((double) *seed / (double) m);
}

This produces a stream of pseudorandom numbers, with the stress on pseudo. Random number generation is hard, and there are many, many bad generators out there--see the Park & Miller article.

The guys on the network security podcast discuss randomness in the context of human perception, which is also a big part of the NPR piece. One of the NSP guys (Rich) referred to people as pattern recognition machines since they will tend to see patterns in randomness. The guest on that episode, Mike Murray, instead refers to people as pattern creation machines: "People create patterns in their heads where randomness occurs."

This discussion is part of a larger one on the undersea cable breaks of early 2008 and, of course, the iPod. Bruce Schneier provides a good, non-technical, short description of pseudorandom number generation: What's a PRNG? It's a mechanism for generating random numbers on a computer. They're called pseudorandom, because you can't get truly random numbers from a completely non-random thing like a computer. In theory, true random numbers only come from truly random sources: atmospheric noise, radioactive decay, political press announcements. If a computer generates the number, another computer can reproduce the process.

An amusing quote from a comment in Schneier's blog: A (non-security/crypto) tale of PRNGs: When I was studying astronomy, a curious result was published: a very narrow (small area of sky), deep (includes very dim galaxies) survey of galaxy red-shifts had been done. (Red-shift corresponds to velocity, which due to expansion of the universe corresponds closely to distance.) The red shifts showed significant periodicity. (I.e. at regular intervals in red shift, there were more or fewer galaxies found.) One of my professors had been doing large computer simulations of large scale structure in the universe. He said "I know what causes this. I've seen it in my simulations. God used a bad random number generator." Posted by: Filias Cupio at June 14, 2006 10:36 PM Footnote: yesterday and today I had my first occasions in awhile to look at C code. One should do this periodically as a reminder of how awful C is. The generator above was originally coded in Pascal, which hasn't been particularly useful for a long, long time.