Transcript History of Random Number Generators

History of Random
Number Generators
Bob De Vivo
Probability and Statistics
Summer 2005
Early RNG’s
•
Dice
o
o
o
o
•
Playing Cards
o
o
•
Used in China for gambling games as early as the 7th century
Introduced to Europe in the late 1300’s
Coins
o
o
•
Forerunners were marked disks or bones, used for betting games
Earliest six-sided dice date from around 2750 B.C.
Found in both northern Iraq and India
Marked with pips, possibly because they pre-date numbering systems
Popular in ancient Rome, from whence they spread across Europe
~ 1900, English statistician Karl Pearson tossed a coin 24,000 times, resulting in 12,012 heads (f = 0.5005)
Spinning Wheels
o
o
Ancient Greeks spun a shield balanced on the point of a spear. The shield was marked into section, and
players would bet on where the shield would stop.
Evolved into fairground wheel of fortune, then into roulette
Types of Modern RNG’s
•
“True” random number generators
o
o
o
o
o
•
Unpredictable (in theory), but slow and possibly biased
Usually based on physical processes, which may be microscopic or macroscopic
Examples:
 Cards, coins, dice, roulette wheels
 Radioactive decay, thermal noise, photoelectric effect
 Keyboard stroke timing, lava lamps, fishtank bubbles
Macroscopic processes are subject to Newtonian laws of motion and are therefore deterministic; they
appear unpredictable, however, because we cannot determine the initial conditions with sufficient accuracy
RNG’s based on quantum properties are completely unpredictable
Pseudo random number generators
o
o
o
o
o
Usually based on a mathematical algorithm
Fast
Suitable for computers
Predictable, if algorithm and initial state are known
Must repeat eventually, since algorithm has finite state, but period may be long enough to avoid repeating on
any conceivable computer within a time span longer than the age of the universe.
John von Neumann
•
•
•
Born 1903 in Budapest
With Stanislaw Ulam, developed a formal foundation for the
Monte Carlo method
In 1951, proposed one of the first pseudo-RNG algorithms for
use on an electronic computer:
Middle-Square Method
 Start with x0, n digits long
 X1 = middle n or n+1 digits of x02
Example:
x0 = 157
1572 = 24649
x1 = 464
Disadvantage: very sensitive to choice of x0
ENIAC, completed
in 1945
Modern Pseudo-RNG’s
•
Linear congruential generators
–
–
–
–
–
•
Mersenne Twister
–
–
–
–
–
•
Form: xn = a * xn-1 + b (mod M)
Most common type of PRNG in use today
Period depends on M, but can be as long as 109 when using 32-bit words
Disadvantage: serial correlation, which means successive numbers are not equidistributed (equally likely to
fall anywhere in the range)
Not suitable for Monte Carlo simulations
developed in 1997 by Makoto Matsumoto and Takuji Nishimura
Very fast
Negligible serial correlation
Period is 219937 − 1 (a Mersenne prime)
Suitable for Monte Carlo, but not cryptography
Blum Blum Shub
–
–
–
–
proposed in 1986 by Lenore Blum, Manuel Blum, and Michael Shub
Not very fast, so poor choice for simulations
Good for cryptography because of the difficulty of finding any non-random patterns through calculation
(strong security proof)
Form: xn+1 = (xn)2 mod(M), where M is the product of two large primes
Mathematica’s RNG
Uses Wolfram rule 30 cellular automaton generator
Table for rule 30:
Evolution of cells, starting
with a single black cell:
Central column
is chaotic