There was a bunch of work done to improve the random number generation algorithms used internally a while back, but if you wanted to have a look at them again, that would be most welcome.
Here is a at least part of the code: https://github.com/plt/racket/blob/master/racket/src/racket/src/random.inc Robby On Wed, Sep 17, 2014 at 7:29 AM, Daniel Prager <daniel.a.pra...@gmail.com> wrote: > Modulo bias is easy enough to correct by checking and occasional > re-sampling. It's explained nicely in the following article: > http://zuttobenkyou.wordpress.com/2012/10/18/generating-random-numbers-without-modulo-bias/ > > Let's *deliberately* generate some modulo bias in Racket by simulating a low > largest random number: > > (define (biased-random RAND-MAX n) > (modulo (random (add1 RAND-MAX)) 3)) > > > (define (check-bias method [n 10000]) > (define sample (for/list ([i n]) (method 4 3))) > > (for ([i (in-range 3)]) > (displayln > (~a i " " (~a (real->decimal-string > (* 100.0 (/ (count (λ (j) (= i j)) sample) n)) > 1) "%"))))) > >> (check-bias biased-random) > 0 38.3% > 1 41.0% > 2 20.7% > > Remove the generated bias by rejecting some "high" values: > > > (define (unbiased-random RAND-MAX n) > (define excess (add1 (modulo RAND-MAX n))) > (define limit (- RAND-MAX excess)) > (define (in-limit m) > (if (<= m limit) m (in-limit (random (add1 RAND-MAX))))) > (modulo (in-limit (random (add1 RAND-MAX))) n)) > > >> (check-bias unbiased-random) > 0 33.9% > 1 33.8% > 2 32.4% > > Conclusion: We should be ok regarding modulo bias provided (random n) uses a > rejection strategy along these lines. If not, it's quite fixable. > > Dan > > On Wed, Sep 17, 2014 at 1:44 AM, Eli Barzilay <e...@barzilay.org> wrote: >> >> On Wed, Sep 17, 2014 at 1:53 AM, Daniel Prager >> <daniel.a.pra...@gmail.com> wrote: >> > >> > [Sorry for drawing you further in.] >> >> :) (Indeed, my main point is that all that random-number stuff is >> foreign to me...) >> >> >> > My take on your 3 points: >> > >> > Fisher-Yates is only a few lines, so although not a one-liner, it >> > seems reasonable to use it for the better space and time performance. >> >> (It's just time -- the space is the roughly same for both, since sorting >> will create an intermediate vector too.) >> >> > I agree that an inside-out version is more apt. >> > On my reading the final point is an issue if (random n) has problems >> > like modulo bias, but if that's the case surely it is (random n) that >> > needs fixing. >> >> It goes into all kinds of arguments that are exactly in that area that >> I'm trying to avoid -- but IIUC, it's hard to avoid module-biases, and >> the FY use of `random' is particularly nasty since it uses all modulos >> in the range of the number of items. See also the point that the WP >> page makes about the size of the random number generator state, and how >> it limits the number of different permutations that can be generated. >> It looks to me like Racket's state is made of 6 fixnums => 2^192 states, >> which still doesn't cover all of the permutations of 52 cards. I have >> no idea if this is correct, if some bias reduces the number of >> permutations, or whether all of this is something to worry about... >> >> -- >> ((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay: >> http://barzilay.org/ Maze is Life! > > > > > -- > Daniel Prager > Agile/Lean Coaching, Software Development and Leadership > Startup: www.youpatch.com > Twitter: @agilejitsu > Blog: agile-jitsu.blogspot.com > > ____________________ > Racket Users list: > http://lists.racket-lang.org/users > ____________________ Racket Users list: http://lists.racket-lang.org/users
