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