Random number generators discussion

Random number generators | www.agner.org

thread fast nonuniform binary random sequence? - Roy - 2011-05-08
last reply fast nonuniform binary random sequence? - Agner - 2011-05-09
fast nonuniform binary random sequence?
Author: Roy Date: 2011-05-08 19:33
I'm looking for a fast method to generate *non uniform* *binary* random sequence (p=0.001 to p=0.1) for monte carlo simulation. I've looked in the usual places, Knuth, numerical recipes, google, and all i can find is:
(a) very fast methods to generate uniform binary sequences (p=0.5), and
(b) very slow methods to generate non-uniform ones.
There appears to be a deep void in-between...

For example, using SFMT, it is possible to generate 128 uniform binary samples (1 full SIMD register) every 3 clocks. so, 128/3= 42bits per clock.

In comparison, generating non-uniform binary sequence by usual method of generating a random number, and then comparing it to a threshold, runs at ~3 clocks per element, ie 0.3 bits per clock.

That's a difference of more than two orders of magnitude (42 vs 0.3)! There must be a better way!

fast nonuniform binary random sequence?
Author: Agner Date: 2011-05-09 05:14
What you need is called the Bernoulli distribution. It is generated simply by
x = r < p;
where r is a uniform random number in 0 <= r < 1, and p is the probability parameter.
It is included in my non-uniform generators package.