Random Number Generator

‧Applications: random sampling, decision making, simulation

‧Random number sequence

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

‧Linear Congruential method:

a0 = seed
ai = (ai-1 * b + 1) mod m

a0: random seed
m: 2^α,10^α
b: 1 digit less than m
.........x21 ， x should be an even

‧Avoid overflow

‧ai = [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

‧Example: m = 10⁸, m1 = 10⁴

P = 10⁴* P1 + P0 q = 10⁴* q1 + q0

=> Pq = 10⁸* P1 * q1 + (P0q1+P1q0) * 10⁴+ P0q0

‧random number belong to [0, r-1] r=2^k

       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

‧‧‧div m

‧random number belong to [0, 1]:a/m

‧Additive Congruential method

‧Linear feedback shift register

(LFSR)

‧Software Implementation

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

‧Need a table size 55 initially generated by Linear Congruential

           [a₅₄ a₅₃ ... a₃₁ ... a₂ a₁ a₀ ]
           [a₅₄ a₅₃ ... a₃₁ ... a₂ a₁ a₅₅]    a₀ <- a₅₅ = (a₀ + a₃₁) mod m
           [a₅₄ a₅₃ ... a₃₁ ... a₂ a₅₆ a₀]    a₁ <- a₅₆ = (a₁ + a₃₂) mod m
                               .                              .
                               .                              .
                               .                              .
           a[j] = (a[j] + a[(j+31) mod 55] mod m

‧Implementation Note

‧2 generators: one generates the table

another picks #

‧Testing Randomness

‧X² - test :

        X² = Σ(0≦i<r)( fi- Pi)²/Pi
             = Σ(i) fi²/ Pi - 2fi + Pi
             = [Σ(i)r / n * fi²] - 2N + N
             = r / n * Σ(0≦i<r)fi²- N

X² - r ≦ 2√r probably "Random" !
> No !!

‧Spectral-test :

......

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