http://www.perlmonks.org?node_id=158491


in reply to Rolling a biased die

Yuck! I think we deserve an O(1) algorithm here, don't you?

With non-integer probabilities, you can do O(log2(n)), but given small n, O(n) is probably a draw (and the code will be simpler).

I suggest normalizing the biases so that they sum to 1.0. Then you can rand(1.0), rather than having to either store or calculate a rand limit.