tag:blogger.com,1999:blog-5246987755651065286.post3064534386664760783..comments2024-02-22T16:15:42.388-08:00Comments on cbloom rants: 02-19-09 - Two Code Gemscbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-5246987755651065286.post-58706174657973547792009-02-19T14:13:00.000-08:002009-02-19T14:13:00.000-08:00A thing that I noticed while reading was that you ...A thing that I noticed while reading was that you are swapping from the 0th element onwards. Whereas the actual shuffle does it from the last element downwards. A small point but I thought I'd point it out regardless.cacapeehttps://www.blogger.com/profile/00475077641183244315noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-34086877083125865862009-02-19T13:28:00.000-08:002009-02-19T13:28:00.000-08:00Ah, wow, that's a good article.In general I have f...Ah, wow, that's a good article.<BR/><BR/>In general I have found that trial-reject-retry is a very easy method to generate correctly distributed randoms with arbitrary probabilities. Hmm I wrote about that before.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-33052211455329306642009-02-19T12:04:00.000-08:002009-02-19T12:04:00.000-08:00And now I notice this is all on Wikipedia, too: ht...And now I notice this is all on Wikipedia, too: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle - damn, could've saved some typing :)ryghttps://www.blogger.com/profile/03031635656201499907noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-37053129867832422542009-02-19T12:03:00.000-08:002009-02-19T12:03:00.000-08:00There's some additional gotchas if you really ...There's some additional gotchas if you really need (or want) your distribution to be as close to actually uniform as possible (online gambling would be an example). The first thing is that you're likely to use a PRNG that outputs a fixed number of random bits (typically 16 or 32). If your "count" is not a power of 2, it's important to note that any function from {0,...,2^n-1} to {0, 1, ..., count-1} will hit some numbers more often that others (this is just the pigeonhole principle). So if you really need the distribution to be perfectly flat, your best bet is to first generate n-bit random numbers where n=ceil(log2(count)) "the usual way", and just reject the ones that are >=count.<BR/><BR/>The other point is that the number of permutations is huge, even for relatively small n. For example, if you're shuffling a deck of 52 cards, your PRNG needs to have a state of at least log2(52!)=225.581... bits to even be theoretically able to produce every possible permutation (you actually want some more bits, again to avoid noticeable bias). A generator with 32-bit state will only ever generate a comperatively tiny subset of all possible permutations.ryghttps://www.blogger.com/profile/03031635656201499907noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-70003262294632920282009-02-19T10:34:00.000-08:002009-02-19T10:34:00.000-08:00rand_mod?rand_mod?won3dhttps://www.blogger.com/profile/09787472194187459747noreply@blogger.com