# Random Number Generator

### ĦEApplications: random sampling, decision making, simulation

#### ĦERandom number sequence

genuine  - impossible with computers
pseudo-random - some good properties of r.n.
quasi-random -

### ĦELinear Congruential method:

 a0 = seed  ai = (ai-1 * b + 1) mod m a0: random seed  m: 2£\,10£\  b: 1 digit less than m      .........x21   ĦA x should be an even

#### ĦEAvoid overflow

ĦEai = [mult(ai-1, b) + 1] mod m
mult(p, q) = {[(P0 * q1 + P1 * q0) mod m1] * m1 + P0 * q0}mod m
 P1 = P div m1,  P0 = P mod m1             q1 = q div m1,  q0 = q mod m1
ĦEExample: m = 108, m1 = 104
 P = 104 * P1 + P0    q = 104 * q1 + q0 => Pq = 108 * P1 * q1 + (P0q1+P1q0) * 104 + P0q0

#### ĦErandom number belong to [0, r-1] r=2k

 a = [mult(a, b) + 1] mod m         (x)  a mod r                      :right K bits         (x)  a * r div m                 :legt K bits         [(a div m1) * r] div m1 (a div m1) * r  ĦEĦEĦEdiv m

### ĦEAdditive Congruential method

#### ĦESoftware Implementation

a[k] = ( a[k-b]  +  a[k-c] ) mod m
Ħò
b = 24
c = 55

#### ĦENeed a table size 55 initially generated by Linear Congruential

[a54 a53 ... a31 ... a2 a1 a0 ]
[a54 a53 ... a31 ... a2 a1 a55]    a0 <- a55 = (a0 + a31) mod m
[a54 a53 ... a31 ... a2 a56 a0]    a1 <- a56 = (a1 + a32) mod m
.                              .
.                              .
.                              .
a[j] = (a[j] + a[(j+31) mod 55] mod m

### ĦETesting Randomness

#### ĦEX2 - test :

X2 = £U(0ĦĜi<r)( fi - Pi)2/Pi
= £U(i) fi2 / Pi - 2fi + Pi
= [£U(i)r / n * fi2] - 2N + N
= r / n * £U(0ĦĜi<r)fi2 - N

X2 - r ĦĜ 2ĦÔr     probably "Random" !
>              No !!

#### ĦESpectral-test :

......
 Pi = N / r  fi = (# r.n. = i )  Totally N r.n.  i.e  fo + ĦEĦEĦE + fr-1 = N