Monday, April 28, 2014

Uniform random number generation in Computer

Let's, have a generator, Ui(Rmax+1), to generate uniform random integer r ∈ [0...Rmax].
We can construct Ui(N) in following way,

Ui(N) =
  1. Range = Rmax - ( Rmax )mod N
  2. do
    1. r = U(Rmax+1);
  3. while( r  ≥  Range );
  4. Return(r);
Similarly, we can further construct a real random number generator Ur(N), which generates random real r ∈ [0,1]. using  Ui(N).

Ur(N) = (N-1)/Ui(N);

Ber(p) = ( Ur(N) ≤ p ) + (Ur(N) > p) ;
Binomial(n,p) =
  1. y = 0
  2. for(i = 0; i < n; i = i + 1)
    1. y = y + Ber(p)
  3. Return y 

No comments:

Post a Comment