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. 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:
- Quotations by John von Neumann on WikiQuote.
- Samuel K. Moore, "PlayStation 3 Processor Speeds Financial-Risk Calculation," IEEE Spectrum Online, November 19, 2008.
- Willie D. Jones, "Intel Makes a Digital Coin Tosser for Future Processors," IEEE Spectrum Online, June 29, 2010.
Permanent Link to this article