[racket] on reversing a list by way of sort

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
>