[racket] on reversing a list by way of sort

I've done some testing of the built-in (random n) and I haven't been able
to detect evidence of modulo bias. Of course absence of evidence isn't
evidence of absence!

More generally though, this is an interesting case (at least to me) of the
trade-offs between efficiency, clarity, concision, cost of learning about a
specialised area as well as arguments from theory vs empirical assessment.

Dan

On Wed, Sep 17, 2014 at 9:14 AM, Robby Findler <robby at eecs.northwestern.edu>
wrote:

> 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.prager at 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 <eli at barzilay.org> wrote:
> >>
> >> On Wed, Sep 17, 2014 at 1:53 AM, Daniel Prager
> >> <daniel.a.prager at 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
> >
>



-- 
*Daniel Prager*
Agile/Lean Coaching, Software Development and Leadership
Startup: www.youpatch.com
Twitter: @agilejitsu <https://twitter.com/agilejitsu>
Blog: agile-jitsu.blogspot.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20140917/2c30d3b8/attachment.html>