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? - Roy - 2011-05-08
fast nonuniform binary random sequence? new - Agner - 2011-05-09