http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
This always bugged me; the obvious way to get_random_int(range) given a binary pool has a modulo bias towards low residues, seen here: http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Modulo_bias There has to be a fix for this that doesn't have an unbounded runtime, based on least-common multiple or something? Assume that your range is 0..n-1. Then the minimum amount of entropy (in bits) is of course b = log_2(n) I was thinking you could pull out the number of bits required (b), and if the result is outside your range, you could try again. Problem is that it's unbounded. Also you may have a fractional bit of entropy that's wasted when you throw away and draw again. If you were to add those up, they will gradually accumulate, but I'm not quite sure how that math adds together. Clearly there are (2^b)-n fractions of residue and they are of 2^b states each. So that won't work. My other idea was to get b bits n times and add them together, but then you get a binomia/normal distribution and not uniform. Ideas? -- http://www.subspacefield.org/~travis/ I'm feeling a little uncertain about this random generator of numbers. -- http://www.subspacefield.org/~travis/ I'm feeling a little uncertain about this random generator of numbers.
pgpFYHZFWyNUz.pgp
Description: PGP signature
_______________________________________________ RNG mailing list [email protected] http://lists.bitrot.info/mailman/listinfo/rng
