Search :
Fall 1993

Research Magazine > ARCHIVE > Fall 93 > Article

Random Numbers
by Judy Purdy

Modern swamis gaze into contemporary crystal balls -- computers -- to forecast events in virtually every profession. From politics and economics to nuclear physics and even war, computer simulations can project trends and predict complex chains of events with what seems to be amazing accuracy.

But recent findings by a team of physicists cast a shadow on a vital component of many computer simulation models -- the random number generator.

Random numbers are the building blocks of many popular and useful computer simulations. If you want to project population growth or test a scientific theory, an accurate prediction often depends on a random number generator to power the computer program.

But are those random numbers truly random?

"Not exactly," said Dr. David P. Landau, a research professor of physics and director of the University of Georgia's Center for Simulational Physics.

Until recently, computer prognosticators thought well-tested, reliable random number generators were good enough for most simulations. Then, quite by chance, Landau, Dr. Alan M. Ferrenberg, a UGA assistant research scientist who works at the University Computing and Networking Services, and Dr. Y. Joanna Wong, a staff scientist at the IBM Corp. Supercomputing Systems Center in Kingston, N.Y., performed a simulation in 1992 that pushed several of the more popular generators beyond the limits of reliability.

The Landau-Ferrenberg-Wong discovery is sending tremors through the computer simulations community. Some researchers are questioning the reliability of their computer-generated forecasts just when they looked like they were the perfect solutions.

"Now that we're capable of doing very precise sorts of simulations, we've discovered sources of error that we didn't necessarily recognize when computers were much slower and when the algorithms were cruder than they are now," Landau said. "The fact that a generator has been used successfully in a dozen different situations and has passed a dozen different tests does not mean that it's going to work well in every situation."

Sophisticated Simulations

Computer simulations have become so powerful and so sophisticated that scientists now can use them to design just about anything. And they are far safer, faster and less expensive than some laboratory experiments.

"A simple example I like to give is: What if we wanted to know would happen in the case of a nuclear war to help us plan in some reasonable way?" Landau said. "We certainly wouldn't want to carry out an experiment to see what would happen. So it was simulated on the computer.

"If you want to attempt to make new materials, very often it's sort of hit or miss. And that's very slow and time-consuming and expensive in the laboratory," he said. "You can now do lots of these things on the computer from making new, more efficient electronic circuits to giving us new understandings of how drugs work to cure disease."

Simulation programs take random numbers and plug them into mathematical formulae that predict probabilities. Random numbers are used daily to make an odd assortment of decisions, from the coin toss at a football game to picking the winning lottery number from a bunch of numbered balls in a basket. Even the Gallup poll relies on random numbers.

For instance, let's say you want to assess American attitudes on health care. "To ask 250 million people or so what they all think is just impossible to do. So you do a random importance sampling," Landau said. "We use the same fundamental approach except, in our case, we randomly sample what goes on with atoms and molecules in a wide variety of systems."

Selecting a random sample is akin to flipping a coin to make a decision, except that coin-tossing computers can be programmed to give you any odds you want.

The accuracy of those odds, however, relies on sound random number generators. Faulty generators may give skewed projections -- or worse, wrong answers. And the consequences range from negligible to severe, depending on the kind of events being modeled, the margin of error you can tolerate and the level of acceptable risk.

"For simulations that forecast the rate of currency exchange on the foreign market, an error of one one-hundredth percent can mean a financial disaster," Ferrenberg said. "But for finding the most efficient information pathways on computer chips or the optimum routing schedule for a transportation company, a margin of error of 1 percent would be more than acceptable."

Fatal flaws

To keep pace with today's high-speed supercomputers, random number generators must concoct millions of numbers per second. And the research Landau and Ferrenberg originally had planned was no exception.

"We were preparing to embark on the most accurate simulation ever to be performed," Landau said.

The simulation modeled how atoms in magnetic crystals undergo changes at high temperatures, causing them to lose their magnetic properties.

"In the most simple model for magnetization, atoms contain little magnets called spin that can point up or down," Ferrenberg said. "Whether it flips up or down depends on what its neighbor is doing. If we flip one atom in the crystal, the probability of all other atoms flipping changes, and we can calculate these. If the probability is greater than the random number, then the spin flips; if it's smaller, then it doesn't flip. Then you move to the next atom and the next and the next, calculating whether the magnetic spin will change."

Understanding magnetic processes are of great importance not only in statistical physics but also in industry, Landau said. For example, computers use magnetic storage, and the center's simulations could provide further insight into ways to revise magnetic materials and change their properties.

But before the two physicists could even run the simulation, they had to assemble a network of computers that would provide the needed power, precision and speed. A mainframe and three smaller computers were configured to operate synchronously. Called a parallel computer network, each component simultaneously and independently works on a segment of the simulation.

They began with a model that would predict exactly how atoms in a simple magnetic system, when heated, would change their magnetic spin up or down. In this simple system, they knew the right answer in advance, so they could compare the simulation answer with the real one. This simple system was a test run for similar but more complex simulations they had planned.

"We looked at one piece of the puzzle to see if it worked," Landau said. "We took a small, two-dimensional element of the program and tested the program on that level."

And that's where they ran into a problem: The answer they got from the computer wasn't the same one they got when they calculated it manually.

"We knew the right answer, but the answer we got from our simulation was simply wrong. We just could not get the computer to give us the right one," Landau said.

When the computers failed to calculate the right answer, Landau and Ferrenberg figured the problem was in their program. Neither suspected the sophisticated random number generator. Repeated program revisions using different techniques followed by additional test runs failed to produce the right answer.

"One of the problems is that these good random number generators don't give you such horrible results that you can immediately tell something is wrong," Landau said. "The answers look quite reasonable and if you're working on a research problem where you don't know the answer, it can be very easy to be misled."

So they decided to get an opinion from Wong, who was part of a UGA/IBM joint research collaboration on parallel computing. After looking at the program, she concluded the program was fine; the problem was caused by the random number generator.

"We weren't prepared for this," Ferrenberg said. "We weren't looking for trouble with random number generators. I spent another three weeks testing the program."

"Most people thought that at the level we were dealing with there wasn't a problem with random number generators, but we discovered that the new and improved random number generators failed," Landau said.

"Random" Solutions

Landau and Ferrenberg are much more skeptical these days. Since their discovery of a major flaw with a random number generator, they have tested six more generators commonly used in simulations. So far, only one has made the grade when it comes to predicting how atoms in magnetic crystals behave at high temperatures.

Scientists have known all along that random number generators weren't perfect. But as long as the generators passed a battery of statistical tests, most scientists accepted them as adequate.

Just five years ago, researchers didn't have these kinds of problems with random number generators, Landau said.

Ultra-powerful computers have changed the landscape of simulation. The difference between the late '80s models and today's lightning-speed parallel networks is "like looking at a flea on a cat and then magnifying it under an electron microscope. It looks like Godzilla," Ferrenberg said.

Today's simulations have greater resolution, which means they also magnify the subtle patterns produced by computer-generated number sequences. These less-than-random numbers amplify the possibility for errors and can skew simulations. Consequently, many "tried and true" random number generators may turn out to be "tried and treacherous."

"Many researchers have known in the back of their minds that these problems are still out there," Landau said. "Our recent finding drives home the point of even greater concern than we thought."

That's why the federal government marks some random numbers series as classified and locks them in vaults.

"Even data encryption methods are based on properties of random numbers," Landau said. "National security has classified random numbers series, and they have teams of people and big computers to protect the accuracy and secrecy of their random numbers. If someone could crack these codes of generating random numbers, they could access their material."

Since December1992, when Ferrenberg, Landau and Wong first published their findings in the journal Physical Review Letters, they have been inundated by requests to test other simulation programs from other research university labs around the world.

"We're concerned that if you're going to do this, you should know what the pitfalls are," Landau said. "For some algorithms, the random number generators work. For others, they don't. We have to look at what's been done in combination with the particular generator.

"When you finish the project, you should have the right answer," he said. "You may not like the answer but at least you should be able to trust it."

But the physicists warn that today's correct answers may be wrong tomorrow.

"In 10 years, when computers are faster and even more sophisticated, we may find these now valid random number generators aren't valid," Ferrenberg said. "We'll continue to look at the problem with new algorithms and faster computers."

For more information go to http://www.physast.uga.edu/people/fac-dpl.html or e-mail csp@uga.cc.uga.edu

Research Communications, Office of the VP for Research, UGA
For comments or for information please e-mail the editor: rcomm@uga.edu
To contact the webmaster please email: ovprweb@uga.edu