Shim, Hyung Jin
Nuclear Engineering Department,
Seoul National University
• Reuven Y. Rubinstein, "Simulation and the Monte Carlo Method," John Wiley &
Sons, Inc., New York (1981).
• C. J. Everett and E. D. Cashwell, "A Third Monte Carlo Sampler" Los Alamos report, LA-9721-MS (1983).
• H. J. Shim, “McCARD Methodology,” SNUMCL/TR001/2010(01), 2012.
• L. J. Gannon and L. A. Schmittroth, “Computer Generation and Testing of Random Numbers,” AEC Research and Development Report, TID-4500 (1963).
References
Monte Carlo Method & Random Number
What is the Monte Carlo method?
• A class of computational algorithms that rely on repeated random sampling to compute their results (Wikipedia)
• A computational method to estimate representative values from the stochastic simulations of a physical or mathematical system using random numbers (H.
J. Shim)
• A method of solving problems using statistics
• A method of solving problems using random numbers
A sequence of random variate generations
by using random numbers
Calculation of PI
An Example of Monte Carlo Method
R R
-R
-R
circle the
inside beans
of number
4 2 2
length side
of square the
of Area
radius of
circle the
of
4 Area
2
2
R
R R
R
Algorithm
① Pick a column number from 1 to 36.
- Roll a dice twice and find an index corresponding to the two numbers from <index map>.
② Pick a row number from 1 to 36.
- Roll a dice twice and find an index corresponding to the two numbers from <index map>
③ Check if the sampled location according to the column and row number is inside the circle.
④ Repeat ①~③ N times and from the results, estimate a PI value.
PI Calculation with a Die
< Index Map >
1,1 → 1 2,1 → 7 3,1 → 13 4,1 → 19 5,1 → 25 6,1 → 31 1,2 → 2 2,2 → 8 3,2 → 14 4,2 → 20 5,2 → 26 6,2 → 32 1,3 → 3 2,3 → 9 3,3 → 15 4,3 → 21 5,3 → 27 6,3 → 33 1,4 → 4 2,4 → 10 3,4 → 16 4,4 → 22 5,4 → 28 6,4 → 34
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
Index Map
What Is the Random Number?
Random Number
• unpredictable number (following the uniform distribution in a certain interval)
• A random number is a number chosen as if by chance from some
specified distribution such that selection of a large set of these numbers reproduces the underlying distribution. Almost always, such numbers are also required to be independent, so that there are no correlations between successive numbers.
(http://mathworld.wolfram.com)
• A number generated for or part of a set exhibiting statistical randomness.
A numeric sequence is said to be statistically random when it
contains no recognizable patterns or regularities; sequences such
as the results of an ideal die roll, or the digits of π exhibit statistical
randomness.
Toss an ideal coin, roll an ideal dice, or draw a ball from an ideal machine
• Takes lots of time.
• Hard to make the ideal equipments.
• Cannot re-generate the random sequence for benchmarking and debugging.
Quantum random number generator (Google it!)
(M. Stipcevic, B. M. Rogina, “Quantum random number generator based on
photonic emission in semiconductors,” Review of Scientific Instruments 78, 045104 (2007).)
• Need a big data storage for exact reproductions of the results
How to Real Random Number & Its Obstacle
Pseudo Random Number
One of the first algorithms for producing random numbers was proposed by von Neumann and Metropolis. This is the mid square method in which each number in the sequence is defined as the middle set of digits of the square of the
previous number.
Consider as an example the first number in the sequence to be 1357 (assume we are working with four digit numbers). Then this number squared is 01841449 and the second number in the sequence becomes 8414, the middle four digits of the squared number.
D. Lehmer points out difficulties that have caused this method to be abandoned. Number of the type 00XY or XY00 soon develop and are either self perpetuating or quickly degenerate to zero.
Mid Square Method
21347 1347 01841449 8414
Multiplicative Congruential Method
• D. H. Lehmer, "Mathematical methods in large-scale computing units," Annals Comp. Laboratory Harvard Univ. 26, 141-146, 1951.
• Generally uses 10b or 2b as P.
• The maximum sequence length for P of 2b becomes 2b-2 with an odd seed number and λ satisfying λ (mod 8) = ±3.
(L. J. Gannon, L. A. Schmittroth, "Computer generation and testing of random numbers," TID-4500, 1963)
Multiplicative Congruential Method (MCM)
1
n
( m o d P )
n
Now, we are going to determine a multiplier
and an initial number
0 for MCMto generate a sequence with the maximum period.
We can make two preliminary observations. The first is that if the multiplier
is even, i.e.,
=2k, the period is very short. In factmeans that
n+b=0 and that the sequence can not be longer than b. Hence,
must be odd in order to obtain a period of any useful length. Likewise, if the initial number
0 is even, the common factor 2 appears both in
0 and the modulus 2b, hence, the modulus is effectively reduced, which reduces the period. Thus
0 must also be odd.Length of Period of Multiplicative Method
1
(mod 2 )
n b
n
(2 ) (mod 2 )
b n bn b
k
We can find the below relation for MCM.
The period means that the length n when the initial random number
0 is regenerated by the congruential method. In order that
n =
0, the following condition should be satisfied Therefore our question becomes to find out
when
n≡1(mod 2b) to maximize n.Determine to Maximize the Period
1 0 1 1 0
2 2
2 1 1 0 2 2 0
0
(mod 2 ) 2
( 2 ) (mod 2 ) 2
(mod 2 )
b b
b b b
n b
n
C
C C
0 ( 2 1) (mod 2 )0
1(mod 2 )
n b b
n n
n b
C
From our earlier observation
has to be odd, and we can represent all odd numbers in the form 8t±1 or 8t±3. We observe thatwhich means that any multiplier
≡±1(mod 8) will generate a sequence whose period is not greater than 2b-3.Determine (Contd.)
3 3 3 3
3 3 3
2 2 2 1 2 2 2
0 1 2
2 2 2
3 3
6 2
(8 1) ( 1) ( 1) 8 ( 1) 8
2 2 1
1 2 2
2 1(mod 2 )
b b b b
b b b
b b
b
b
t C C t C t
t t
We next show that a multiplier
≡±3(mod 8) leads to a sequence with a period greater than 2b-3.Determine (Contd.)
3 3 3 3
3 3 3
3 3 3
3
2 2 2 1 2 2 2
0 1 2
2 2 2
3 3
2 2 1 6 2 2 2
2
(8 3) ( 3) ( 3) 8 ( 3) 8
2 2 1
3 2 ( 3) 2 3
2 3 (mod 2 )
b b b b
b b b
b b b
b
b b
b
b
t C C t C t
t t
3 3 3 3 3
3 3 3
2 2 2 2 1 2 2 2
0 1 2
2 2 2
3 3
3 4
1
3 (4 1) ( 1) ( 1) 4 ( 1) 4
2 2 1
1 2 4 2
2 1 2
b b b b b
b b b
b b
b
b
C C C
1(mod 2 )b
We then try 2b-2.
So the period of
≡±3(mod 8) is 2b-2. The maximum sequence length for P of 2b becomes 2b-2 with an odd seed number
Determine (Contd.)
2 2 2 2
2 2 2
2 2
2
2 2 2 1 2 2 2
0 1 2
2 2 2
2 2 2 1
2
(8 3) ( 3) ( 3) 8 ( 3) 8
3 2 3 8
3 (mod 2 )
b b b b
b b b
b b
b
b
b
t C C t C t
t
2 2 2 2 2
2 2 2
2 2 2 2 1 2 2 2
0 1 2
2 2 2
2 2
2 4
3 (4 1) ( 1) ( 1) 4 ( 1) 4
2 2 1
1 2 4 2
2 1(mod 2 )
b b b b b
b b b
b b
b
b
C C C
Additive Multiplicative Congruential Method
• A. Rotenberg, "A new pseudo-random number generator," J. Assoc. Comput., Mach. 7, 1960.
• The maximum sequence length for P of 2b becomes 2b with an odd seed number, an odd μ, and λ of 2a+1(a>2).
(L. J. Gannon, L. A. Schmittroth, "Computer generation and testing of random numbers," TID-4500, 1963)
Additive Multiplicative Congruential Method(AMCM)
n mod P
1
n
The MCM and AMCM have been widely used for various workstation and Monte Carlo codes.
Quasi-Random Number
From a sequence of n-tuples that fills n-space more uniformly than uncorrelated random points generated by MCM or AMCM, extremely-accurate results could be
Examples of RNG’s
Name Equation
Janet Nicholls (a) CRAY Library MCNP Code (b) GNU-C Library
481
2e90edd
(16)mod 2
n
n
481
2875a2e7b175
(16)mod 2
n
n
481
1158e460913d
(16)mod 2
n
n
481
5deece66d
(16)b
n (16)mod 2
n
(a) Janet Nicholls, "Random number generators," AECL-3476, 1969.
(b) J. F. Briesmeister, Ed., "MCNP - A General Monte Carlo N-Particle Transport Code, Version 4A," LA-12625-M, 1993.
Implementation of AMCM – 1/3
A random number from the additive multiplicative method can be obtained by
To implement Eq. (1) in a computer language (C, C++, etc.), the
parameters of Eq. (1) – , and – should be expressed in small-sized variables such as ‘unsigned short’(two bytes) or ‘unsigned char’ (one byte) enough for a large-sized variable to store a multiplied value by a small-sized variable.
In this implementation, and are divided into three 2-byte (‘unsigned short’) variables as
(1)
(2)
1
mod 2
48n n
32 16 16
2 1 0
32 16 16
2 2 ; 2 ( 0,1, 2)
2 2 ; 2 ( 0,1, 2)
i
i
i
Implementation of AMCM – 2/3
The substitution of Eq. (2) into Eq. (1) leads to
Let’s treat terms in I with dividing ‘short’ variables.
• can be stored in a ‘unsigned long’ variable (four bytes) because
• To divide into two 2-byte variables, two operators are defined as
1 32 16 32 16 48
2 1 0 2 1 0
16 16 32 32 32
0 0 1 0 0 1 2 0 1 1 0 2
64 48 48
2 2 2 1 1 2
2 2 2 2 mod 2
2 2 2 2 2
+ 2 2 2
n n n n
n n n n n n
n n n
mod 2
48 (3)I
0 0
n32
0
0 0n 2 .
0 0
n16
16
16( )
2
16( ) mod 2 UP X X
LO X X
(4)
By treating the other terms of the right hand side in the same way for I, Eq. (3) can be written as
Implementation of AMCM – 3/3
1 16 16 32 32 32 48
0 0 1 0 0 1 2 0 1 1 0 2
32 16
2 3 4 5 2 0 1 1 0 2 5 1
2 2 2 2 2 mod 2
16 2 2
n n n n n n n
U U U U n n n L L
LO
(6)0U
UP 16
0 0n,
0LLO 16
0 0n
1 0 1 0
2 0 1 2 0 1
16 , 16 ,
16 , 16
U L L L
U U U L U U
UP LO
UP LO
3 1 0 3 1 0
4 0 1 4 0 1
16 , 16 ,
16 , 16 ,
U n L n
U n L n
UP LO
UP LO
In order to handle sequence of random numbers for a certain particle simulation, it is required to set a seed number to a prescribed value. Especially, this adjustment is required for parallel computations with the same random number sequence applied in a single processor run.
For a given striding number l, the l-th random number by AMCM can be written as
l can be obtained from Eq. (6) setting the seed number to 0 and calculating the l-th random number. And
l can be obtained from Eq. (6) by setting the seed value to 1 and the
to 0 and calculating the l-th random number. Then
l and
l can be expressed in two-byte variables asControl of Random Number Sequence
1 48 48
0
48 1 48
0
mod 2 mod 2 ;
mod 2 , mod 2 .
l l p
n l n l n l
p
l l p
l l
p
(7)
(2) 232 (1) 216 (0); ( )i 2 (16 i 0,1, 2),
Substituting
l and
l of Eq. (8) in Eq. (7) and applying the HI16 and LO16 operators, Eq. (7) can be written asControl of Random Number Sequence (Contd.)
(0) (0) (0) (1) (0) 16 (0) (1) 16 (1) 16
48
(2) (0) 32 (1) (1) 32 (0) (2) 32 (2) 32
(0) (0) (0) (0) (0) 16
(1) (0) 16 (1) (0) 32
2 2 2
mod 2
2 2 2 2
16 16 2
16 2 16 2
n n n
n l
n n n
n n
n n
LO HI
LO HI
(0) (1) 16 (0) (1) 32 (1) 16 48
(2) (0) 32 (1) (1) 32
(0) (2) 32 (2) 32
(0) (0) (0)
(0) (0) (0) (0
16 2 16 2 2 mod 2
16 2 16 2
16 2 2
16 16
16 16 16
16
n n
n n
n
n
n
LO HI
LO LO
LO
LO LO
HI LO HI
LO
) (0) 16
(1) (0) (0) (1) (1)
(0) (0) (0) (0) (0)
32
(1) (0) (0) (1) (1)
16 16 2
16 16 16
16 2
n
n n
n n
LO LO
HI LO HI
HI
Then the every l-th random number
n+1 can be obtained byControl of Random Number Sequence (Contd.)
2 3 4 5 6 7 8 (2)
32 5 16 116 U U U U L L L 2 L2 L
n l LO
(0) (0) (0) (0)
0 0
(0) (0)
1 0 1 0
2 0 1 2 0 1
(1) (0) (1) (0)
3 3
(0) (1) (0) (1)
4 4
5 2
16 , 16 ,
16 , 16 ,
16 , 16 ,
16 , 16 ,
16 , 16 ,
16
U L
l n l n
U L L L
l l
U U U L U U
U L
l n l n
U L
l n l n
U
HI LO
HI LO
HI LO
HI LO
HI LO
UP
(1) (1)
3 4 5 2 3 4
(2) (0) (1) (1) (0) (2)
6 7 8
, 16 ,
16 , 16 , 16 .
L L L L L L L
l l
L L L
l n l n l n
LO
LO LO LO
(9)
Requirements for the random numbers
① Not correlated between the sampled numbers
② Uniformly distributed
③ Rapidly generated
④ Re-producible
⑤ have a large cycle length
Various tests
• Uniform distribution
frequency test, subsequence frequency test
• No correlation
matrix test, auto correlation test, running length test, slice test
• Reuven Y. Rubinstein, "Simulation and the Monte Carlo Method," John Wiley
Randomness Test
Algorithm for Frequency Test
① Generate a random number .
② Find a subinterval i satisfying
③ Increase the frequency in i-th interval (f
i) by 1.
④ Repeat ①~③ N of times (N=10240).
⑤ Calculate the chi-square value:
⑥ Compare this chi-square value with the chi-square distribution with 1023 degrees of freedom which has a 95 percent confidence interval of
22
1
K i i
i i
f E
E
expected number in subinterval 10240 1024 10
Ei i N K
the observed frequency in subinterval
f
i i
936.3
2 1113.5 .
1 ( 1024 and 1, 2, , ).
i i
K i K
K K
Application Results of Frequency Test
936.3 2 1113.5
Test Idx. Nicholls CRAY MCNP GNU C
1 1074.6 1017.2 1080.6 1047.2
2 983.4 971.8 1022.8 1085.0
3 1041.4 1023.4 1019.4 950.2
4 1020.4 972.4 940.4 991.2
5 1053.4 980.0 954.4 1056.6
6 1009.4 999.2 1122.8 1036.2
7 1069.8 1052.0 925.8 989.8
8 924.6 946.0 962.6 978.0
9 1062.6 1062.4 1023.4 1055.2
10 1062.0 1049.4 1044.8 1121.8
Implementation of Frequency Test
Implementation of Matrix Test
Algorithm
① Generate a random number
.② If
is less thane
(=0.01), then generate two random numbers (
X,
Y) and plot it as X=
X, Y=
Y.③ Repeat ①~② until the number of plots is equal to 1024.
(E. Musyck, "Search for a perfect generator of random numbers," BLG-516, 1977)
Slice Test
0.0 0.2 0.4 0.6 0.8 1.0
0.0 0.2 0.4 0.6 0.8 1.0
Y
0.0 0.2 0.4 0.6 0.8 1.0
0.0 0.2 0.4 0.6 0.8 1.0
Y
Congruence
• If two numbers b and c have the property that their difference is divisible by a number m (i.e., (b-c)/m is an integer), then and are said to be “congruent
modulo m.” The number m is called the modulus, and the statement “b is congruent to c (modulo m)" is written mathematically
Residue Class
• A class of all integers which are mutually congruent for a given modulus.
• The residue classes of a function f(x) mod m are all possible values of the residue f(x) (mod m). For example, the residue classes of x2 (mod 6) are {0,1,3,4}, since
Several Concepts from Number Theory
(mod )
b c m
2 2 2
2 2 2
0 (mod 6) 0,1 (mod 6) 1, 2 (mod 6) 4 3 (mod 6) 3, 4 (mod 6) 4,5 (mod 6) 1,
Complete Residue System
• A complete residue system modulo m is a set of integers which satisfy that every integer is congruent to a unique member of the set modulo m.
• For example {1,2,3}, {4,5,6}, and {9,17,85} are all complete residue systems (mod 3).
• For a given modulus m, a set of m numbers congruent in some order to the residues 0, 1, …, m-1.
• What’s the complete residue system for x2 (mod 6)?
Reduced Residue System
• A reduced residue system modulo m can be formed from a complete residue system modulo m by removing all integers not relatively prime to m.
• For example, a complete residue system modulo 12 is
{0,1,2,3,4,5,6,7,8,9,10,11}. 1, 5, 7, and 11 are the only integers in this set
Several Concepts from Number Theory (Contd.)
{ (0)(mod ), (1)(mod ), , ( f m f m f m 1)(mod )} m
Euler’s phi-function,
j
(m)• Denotes the number of integers less than m and prime to m.
• For example,
