Brain Candy #60 - New Clear Science

In a recent Brain Candy column (twice actually, in BC #37 and #56), I discussed a few sections of the Fourmilab website, www.fourmilab.to, which focuses on science, engineering and computing topics. I saved one of the sections, Hotbits, for a future column - this one. Hotbits is devoted to the generation of truly random numbers; you can find it at www.fourmilab.ch/hotbits/.

If you're not up on random number generation, it can be very serious business for scientists and programmers. It's not such a big deal if your targets in Quake aren't selected with perfectly random numbers, but if you're basing your dissertation on a simulation that uses random numbers, a less than perfect random number generator might lead you to some embarassing conclusions.

In the old days, there were tables of random numbers you could consult. Now most people opt for a less tedious way to access random numbers, especially when a lot of them are needed. Computers can be useful, but you shouldn't just grab a computer as it comes off-the-shelf to generate random numbers. Computers have random number generator software built in, but many of these routines are known to have serious flaws. Some numbers may come up too often or too rarely, they may show serial correlation (numbers which show a non-random relationship to previous numbers) or they may begin to repeat themselves after generating only a small number of random numbers. Historical reviews of random number generation often mention that in the early days of computing, someone put a poor-quality random number generator, called RANDU, in their Big Blue computer, which has been copied by others innumerable times ever since. Others, realizing the flawed nature of RANDU, implemented equally flawed variants or different, but still flawed, algorithms. Experts believe that even today, most computers have poor built-in random number generators. And yes, dissertations have been ruined because of them.

The real issue is that software inherently isn't capable of random behavior. If I know the random number algorithm in use, and I enter "x" as a seed number, I'll always know what "y" will be. Software can simulate randomness, but cannot by itself be random. Most researchers don't think the theory of software random generators is sufficiently advanced to identify an ideal software random number generator, but there do appear to be some relatively good software random number generators. See random.mat.sbg.ac.at/generators for more details.

True randomness requires a random process - think hardware. This is where Hotbits comes in. Radioactive decay is a known random process. Given a radioactive atom, one can know what the probability of a radioactive decay will be, but there is no way, even in theory, to know precisely when a particular atom will actually decay. Going further, if you don't know when any particular atom will decay, you don't know when the next one in a group of atoms will decay, nor do you know how far apart the next two decays will be. This last fact allows one to create a random number generator from a radiation detector by measuring two between-decay time periods. If the first between-decay period is shorter than the second, the software watching the counter emits a "0", while if it is longer, the software emits a "1". Collect enough of these zeros and ones and you can create a base-two number, which, if you set up your system to avoid any biases, will be completely random. Convert it to a base-ten number, and you've got your random number.

The Hotbits site provides visitors with a limited number of random numbers, but its main interest is in describing how the process is done: the theory, the hardware, and the software needed to set up this kind of a random number generator is presented. If you're a bit handy with a soldering iron, have a few dollars and an unused computer to spare, and don't mind handling radiation sources, you should be able to build your own Hotbits random number generator. All the info you need is at Hotbits, including what to buy and where to buy it.

You don't need a radiation source and counter to build a hardware random number generator, of course. There are other random processes going on in the world. Random electronic noise can be measured to get random bits. There are other ways, too. One creative group at Sun Microsystems pointed a camera at a group of lava lamps and at regular intervals captured a picture that was processed in such a way to extract random numbers. Sadly, the original site has been removed at the "request" of corporate lawyers. A new, non-Sun site is in the works, but not yet operating. You can find the "coming soon" information about this site at www.lavarnd.org.