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) =
We can construct Ui(N) in following way,
Ui(N) =
- Range = Rmax - ( Rmax )mod N
- do
- r = U(Rmax+1);
- while( r ≥ Range );
- Return(r);
Ur(N) = (N-1)/Ui(N);
Ber(p) = ( Ur(N) ≤ p ) + (Ur(N) > p) ;
Binomial(n,p) =
Binomial(n,p) =
- y = 0
- for(i = 0; i < n; i = i + 1)
- y = y + Ber(p)
- Return y