Tikalon Header Blog Logo

Random Computing

July 26, 2010

Random numbers are an important part of scientific simulation and computer modeling. Computer generation of random numbers is an oxymoron, as John von Neumann famously stated[1]
Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.
What von Neumann was saying is that the numbers aren't random if we know how to generate them. He used computer-generated random numbers, nonetheless, in his Monte Carlo calculations. Von Neumann invented a nice method, called "Von Neumann Whitening," to increase the randomness of bit streams.

I've worked with randomness all my life. At the same time that men first landed on the moon, I was building a random digit display using a common method of generating random voltages (a.k.a., white noise) in analog circuitry. My earliest digital random number generator was a linear feedback shift register (LFSR) that used TTL integrated circuits. Finally, personal computers became available, and it was possible for me to program a computer to act like the hardware LFSRs I had built. The Linear Congruential Generator is an easier way to program random numbers, but its randomness is considered somewhat worse than that of a LFSR. Random number generators are now built into most computer languages, although purists, noting von Neumann's statement, prefer to roll their own. One popular generator is the Mersenne Twister, which seems to have enough code thrown at the problem to make the best random numbers possible.

A sixteen-stage linear feedback shift register

A sixteen-stage linear feedback shift register. Bits 11, 13, 14, 16 are combined by exclusive-or gates to give a maximal length (65535 bit) random bit generator


Sometimes, the unique computer architectures present in gaming systems can lead to improvements in random number generation. David A. Bader, a professor at the Georgia Institute of Technology, and two of his graduate students, Aparna Chandramowlishwaran and Virat Agarwal, adapted the Mersenne twister to the Cell chip used in the Sony PlayStation 3, to substantially increase the speed of Mersenne Twister random number generation.[2]

One way to heed von Neumann's advice is to stop using algorithmic methods of generating random numbers and go back to physical noise sources, such as the white noise voltage generator I built forty years ago. It would be nice to build a white noise voltage generator into a computer chip, but the fundamental problem is that these chips are digital, and the required circuitry is analog. Sure, each type of circuit is based on the transistor, but the transistors are optimized for different performance requirements, so digital chips only do digital things well.

Intel has devised a way to incorporate analog randomness into a digital random number generator.[3] A research team at Intel's Circuit Research Lab (Hillsboro, Oregon) has built a random number generator using the Intel standard CPU process. This generator can produce billions of random bits per second. Intel's team utilized the randomness inherent in the transistor transition between low voltage (digital "0") and high voltage (digital "1") states. Transistor data are sampled during this period, and, with tuning, the samples are randomly ones or zeros. I'm somewhat suspicious about the "tuning" part, but we'll monitor their progress. I'm certain the cryptographers will be more than willing to analyze the bit stream from this generator when the chip is available.

References:

  1. Quotations by John von Neumann on WikiQuote.
  2. Samuel K. Moore, "PlayStation 3 Processor Speeds Financial-Risk Calculation," IEEE Spectrum Online, November 19, 2008.
  3. Willie D. Jones, "Intel Makes a Digital Coin Tosser for Future Processors," IEEE Spectrum Online, June 29, 2010.

Permanent Link to this article

RSS Feed

Google Search


Free Downloads:
STEM artwork
for your holiday gifts

STEM art images

Latest Books by Dev Gualtieri

LGM by Dev Gualtieri
LGM by Dev Gualtieri, paperback LGM by Dev Gualtieri, Kindle

Thanks to Cory Doctorow of BoingBoing for his favorable review of Secret Codes!

Secret Codes & Number Games by Dev Gualtieri
Secret Codes & Number Games by Dev Gualtieri, paperback

Other Books

Other Books by Dev Gualtieri