Take a chance: scientists put randomness to work

Science News, Dec 4, 2004 by Erica Klarreich

Since the dawn of written history, people have exploited the randomness of a roll of a die to inject their games with the thrill of the unpredictable. Today, randomness is finding myriad other uses, such as encrypting credit card numbers in Internet transactions, deciding how to allocate treatments in drug trials, choosing precincts to call in national polls, running online gambling sites, and helping physicists simulate phenomena ranging from the weather to traffic patterns. These applications, however, require many more random numbers than can be obtained from rolling a die. A busy commercial Web site, for example, uses hundreds of thousands of random numbers every minute to mask its users' credit card numbers. And in the research world, computer simulations eat up millions of random numbers in a matter of seconds. To accommodate these needs, researchers are creating a precise science out of something at which toddlers excel: making chaos at breakneck speed.

Randomness is a slippery concept, easier to talk about than to define. Scientists instead tend to say what it isn't. A random number is one that can't be predicted.

Knowing some of the random numbers in a list doesn't make it easier to figure out the others. Over the past few decades, computer scientists have designed computer algorithms that produce a good approximation of true randomness. These algorithms churn out long sequences of pseudorandom numbers, which are scattered about the number line in roughly the same distribution as random numbers are. These pseudorandom numbers are unpredictable enough for many, but not all, purposes.

Now, physicists and computer scientists are figuring out ways to pull true randomness out of the physical world. One Web site, for instance, generates random numbers from the noise of a radio tuned between stations. And a commercial device put on the market last March harnesses nature's ultimate source of randomness: quantum physics, which Albert Einstein famously described as God playing dice.

APPROXIMATELY RANDOM Although computers are expert at spewing out numbers, a computer program can't by itself produce random ones. Computers are engineered to behave deterministically, obeying the will of their users. "If a computer does something unpredictable, then we call it broken,' says Landon Noll, a cryptographer at the computer security firm SystemExperts in Sudbury, Mass.

However, computer scientists have figured out how to produce computer-generated sequences of numbers that are virtually indistinguishable from random numbers. To get a sense of how these algorithms operate, consider the following highly simplified version of a pseudorandom-number algorithm.

First, it's necessary to choose a starting number between 0 and 12, called the seed--say, the number 4. After that initial choice, the algorithm produces each new pseudorandom number by multiplying the preceding number by 17, dividing the result by 13, and taking the remainder.

This particular algorithm is a far cry from randomness, since it quickly falls into a pattern. The first few numbers in the sequence are 3, 12, 10, 1, and then 4, which brings us back to where we started. After that, the sequence simply repeats itself indefinitely.

All pseudorandom-number generators eventually fall into a repeating pattern. However, an algorithm that produces an extremely long pattern before repeating can be unpredictable enough to suit many purposes. Mathematicians have constructed effective pseudorandom-number generators similar to the above algorithm by using larger numbers than 17 and 13 and more-complicated procedures for generating the next number in the sequence. One widely used pseudorandom number generator along these lines is the Mersenne Twister, designed in 1997, which produces a sequence of [2.sup.19,937]-1 numbers before repeating.

Pseudorandom-number generators are key to computer simulations of complicated physical systems. For example, to search for the characteristic shape into which a protein molecule will fold, researchers start with one possible shape and then make small, random changes in it, checking the stability of each new shape. Whenever the shape has gotten more stable, they replace the old one with the new. Then they repeat the same process, sometimes thousands of times.

Similar processes are used to simulate a wide range of phenomena, including weather, traffic flow, stock market swings, and radiation therapy for cancer.

A large simulation can swallow up tens of billions of random numbers. As a result, researchers put a high premium on the efficiency of the pseudorandom-number generator they use. The Mersenne Twister, which is one of the fastest pseudorandom-number generators around, is a popular choice.

Other pseudorandom-number generators are also widely used, including some that have serious flaws, says David Wagner, a computer scientist at the University of California, Berkeley. For example, many computers come equipped with a random-number generator that alternates between odd and even numbers. A truly random sequence would never have such a regular structure.