Transcript Random Number Generator

2110301 Intro. to Discrete Structures
Prabhas Chongstitvatana
Random Number Generator
December 1999
Prabhas Chongstitvatana
1
What is random number ?
Sequence of independent random numbers
with a specified distribution such as uniform
distribution (equally probable)
•Tippett 1927 published a table of 40,000
random digits
•Kendall and Babington-Smith 1939 built a
machine to generate random number to
produce a table of 100,000 random digits.
December 1999
Prabhas Chongstitvatana
2
Jon von Neumann 1946 suggested the production
of random number using arithmetic operations of
a computer, "middle square", square a previous
random number and extract the middle digits,
Example generate 10-digit numbers,
was 5772156649, square
33317792380594909201
the next number is 7923805949
December 1999
Prabhas Chongstitvatana
3
The sequence is not random, but it appears to be.
Sequences generated in a deterministic way are
usually called pseudo-random sequences.
"middle square" has proved to be a comparatively
poor source of random numbers. If zero appear as
a number of the sequence, it will continually
perpetuate itself.
Random numbers should not be generated
with a method chosen at random. Some theory
must be used.
December 1999
Prabhas Chongstitvatana
4
The use of random numbers
1. simulation
2. sampling
3. numerical analysis
4. computer programming
5. decision making randomness is an
essential part of optimal strategies in the
theory of games
6. recreation
December 1999
Prabhas Chongstitvatana
5
Linear Congruential Method
x n+1 = ax n + c ( mod m ), 0 <= x n+1 < m
m > 0, 2 <= a < m, 0 <= c < m, 0 <= x 0 < m.
Theorem The terms of the sequence generated by the
linear congruential method are given by
x k = a k x 0 + c(a k - 1) / ( a -1 ) (mod m ), 0 <= x k < m.
December 1999
Prabhas Chongstitvatana
6
Proof by mathematical induction. for k = 1 , the formula
is obviously true, since
x 1 = ax 0 + c ( mod m), 0 <= x 1 < m.
Assume that the formula is valid for the k th term, so that
x k = a k x 0 + c(a k - 1) / ( a -1 ) (mod m ), 0 <= x k < m.
Since
x k+1= a x k + c (mod m ), 0 <= x k+1 < m.
we have
x k+1 = a( a k x 0 + c(a k -1)/(a-1)) + c
= a k+1 x 0 + c(a(a k -1)/(a-1) + 1
= a k+1 x 0 + c(a k+1 -1)/(a-1) (mod m)
December 1999
Prabhas Chongstitvatana
7
which is the correct formula for the (k+1)th term.
This demonstrates that the formula is correct for
all positive integers k.
The period length of a linear congruential pseudorandom number generator is the maximum length
of the sequence obtained without repetition.
Theorem The linear congruential generator
produces a sequence of period length m if and
only if (c,m) =1 , a = 1 (mod p) for all primes p
dividing m, and a = 1 (mod 4) if 4 | m
December 1999
Prabhas Chongstitvatana
8
For the proof see D. E. Knuth, “The art of
computer programming” vol 2, “seminumerical
algorithms”, 2nd ed Addison Wesley, 1981. pp.
9-20.
A special case where c = 0 is called
multiplicative congruential method.
x n+1 = a x n ( mod m), 0 < x n+1 < m.
or
x n = a n x 0 (mod m), 0 < x n+1 < m.
December 1999
Prabhas Chongstitvatana
9
For many applications, the generator is used
with the modulus m equal to the Mersenne
prime M31 = 2 31 -1.
When the modulus m is a prime, the maximum
period length is m -1, and this is obtained
when a is a primitive root of m.
Find a primitive root of M 31
December 1999
Prabhas Chongstitvatana
10
Number Theory
“Elementary number theory and its applications”, 2ed, K.
Rosen. Addison-Wesley, 1988.
Definition Let m be a positive integer. If a and b
are integers, we say that a is congruent to b
modulo m if m | (a-b), denoted by a = b (mod m).
Definition. The integers a and b are called
relatively prime if a and b have greatest common
divisor (a,b) = 1.
December 1999
Prabhas Chongstitvatana
11
Definition . Let n be a positive integer. The
Euler phi-function p(n) is defined to be the
number of positive integers not exceeding n
which are relatively prime to n.
December 1999
Prabhas Chongstitvatana
12
Euler’s theorem. If m is a positive integer and a
is an integer with (a,m) = 1, then
a p(m) = 1 (mod m).
Definition. Let a and m be relatively prime
positive integers. Then the least positive integer
x such that
a x = 1 (mod m) is called the order of a modulo
m denoted by ord m a.
December 1999
Prabhas Chongstitvatana
13
Example Find the order of 2 modulo 7.
2 1 = 2 (mod 7), 2 2 = 4 (mod 7), 2 3 = 1 (mod 7).
Therefore ord 7 2 = 3.
Definition . If r and n are relatively prime
integers with n > 0 and if ord n r = p(n) , then r is
called a primitive root modulo n.
December 1999
Prabhas Chongstitvatana
14
Theorem 1 If ord m a = t and if u is a positive integer,
then
ord m (a u ) = t / (t,u)
Corollary 1 Let r be a primitive root modulo m where m
is an integer m > 1. Then r u is a primitive root modulo
m if and only if (u, p(m) ) = 1.
Proof By Theorem 1 we know that
ord m r u = ord m r / (u, ord m r ) = p(m) / (u, p(m) ).
Consequently, ord m r u = p(m), and r u is a primitive
root modulo m, if and only if (u, p(m)) = 1.
December 1999
Prabhas Chongstitvatana
15
To find a primitive root of M 31 that can be used
with the good results, we first demonstrate that 7 is
a primitive root of M 31
Theorem The integer 7 is a primitive root of
M 31 = 2 31 - 1.
Proof To show that 7 is a primitive root of M31, it
is sufficient to show that
7 (M 31 - 1)/q /= 1 ( mod M 31)
for all prime divisors q of M 31 -1. With this information
we can conclude that ord M 31 7 = M 31 -1.
December 1999
Prabhas Chongstitvatana
16
To find factorization of M 31 -1, we note that
M 31 - 1 = 231 -2
= 2(230 - 1)
= 2(215 - 1)(215 + 1)
= 2(25-1)(210+25+1)(25+1)(210-25+1)
= 2.32.7.11.31.151.331
if we show that
7(M31 -1 )/q /=1 (mod M31)
for q = 2,3,7,11,31,151,331, then we know that 7 is a
primitive root of M31 = 2147483647.
December 1999
Prabhas Chongstitvatana
17
Since
7(M31 -1)/2 = 2147483546 /= 1 (mod M31)
7(M31 -1)/3 = 1513477735 /= 1 (mod M31)
7(M31 -1)/7 = 120536285 /= 1 (mod M31)
7(M31 -1)/11 = 1969212174 /= 1 (mod M31)
7(M31 -1)/31 =
512 /= 1 (mod M31)
7(M31 -1)/151 = 535044134 /= 1 (mod M31)
7(M31 -1)/331 = 1761885083 /= 1 (mod M31)
we see that 7 is a primitive root of M 31.
December 1999
Prabhas Chongstitvatana
18
In practice we do not want to use the primitive
root 7 as the generator, since the first few integers
generated are small. We find a larger primitive
root using Corollary 1. We take a power of 7
where the exponent is relatively prime to M31 - 1.
For instance, since (5,M31 - 1) = 1, Corollary 1
tells us that 75 = 16807 is also a primitive root.
Since (13,M31 -1 ) = 1, another possibility is to
use 713 = 252246292 (mod M31) as the multiplier.
December 1999
Prabhas Chongstitvatana
19
Choice of modulus
Let w be the computer’s word size, or 2 e
on an e-bit binary computer. Use
m = w + - 1.
Why not m = w ?
When m = w the right-hand digits of x n
are much less random than the left-hand
digits.
December 1999
Prabhas Chongstitvatana
20
If d is a divisor of m, and if
y n = x n mod d
we can easily show that
y n+1 = (a y n + c ) mod d
for x n+1 = a x n + c – qm for some integer q,
and taking both sides mod d cause the quantity
qm to drop out when d is a factor of m.
This shows that the low-order form a
congruential sequence that has a period of
length d or less.
December 1999
Prabhas Chongstitvatana
21
Other generators
Linear congruential method can be generalized to, say, a
quadratic congruential method
x n+1 = ( d x 2 n + a x n + c ) mod m
additive number generator (Mitchell and Moore 1958)
x n = (x n-24 + x n-55) mod m , n >= 55
m is even, x 0 . . . x 54 not all even. The least significant
bits “x n mod 2” have a period of length 255 – 1.
Therefore the generator must have a period at least this
long.
December 1999
Prabhas Chongstitvatana
22