Re: [Chicken-hackers] [C5] About `random` and its future

[Jim Ursetto]

You could use random-bsd as a drop-in replacement if you want.

http://api.call-cc.org/doc/random-bsd

> On Sep 17, 2017, at 12:43 PM, lemonboy <address@hidden> wrote:
> 
> Hello hackers,
> this time there's no patch and no code involved. I recently had some code that
> used the `random`/`randomize` duo from the `extras` module to do some 
> operations
> on some data. The code came with a modest test suite that worked just fine on 
> my
> laptop but failed when run on other systems running different OSs because of 
> the
> different underlying PRNG implementation used by `random()`.
> 
> Many programming languages offer in their standard library a portable and
> standardized PRNG beside the system's one (or, better, the libc's one) to
> provide a uniform and coherent experience across all the supported systems and
> avoid problems such as the one described just above.
> 
> AFAICT the `extras` module contains a bunch of useful procedures to get one
> started writing so it'd be nice if we could choose and implement a single 
> PRNG,
> taking advantage of the (light) breakage introduced by C5.
> 
> Of course shopping for a PRNG is no easy task so I did some research to get 
> the
> ball rolling, here's a list of contenders:
> 
> * SplittableRandom (aka splitmix64)
>  url: 
> https://www.researchgate.net/publication/273188325_Fast_Splittable_Pseudorandom_Number_Generators
>  (there's a small errata in the paper as outlined here [1])
> 
>  Used by Java, it is pretty simple to implement and has a state consisting of 
> a
>  single u64. There are a few minor caveats with this PRNG like the "small"
>  period of 2^64, I don't think that's a big problem for our use-case.
>  The nice thing about this PRNG is the ability to "split" a single stream but 
>  we may not really need it since CHICKEN is effectively single-threaded (let's
>  have each fork()'ed process have its own stream instead ?)
> 
> * xorshift128+
>  url: http://www.jstatsoft.org/v08/i14/paper / http://xoroshiro.di.unimi.it
> 
>  Implemented by rust, v8, Nim and a few other. Simple in its implementation 
> and
>  very compact (2 u64s) and it has a "big enough" period, it must be carefully
>  seeded [2]. It's been replaced by xoroshiro128 which sports similar qualities
>  and better statistical properties and it's being used in Erlang's OTP library
>  in a slightly different variant made to produce 58bit numbers.
> 
> * ISAAC / ChaCha{12,20}
>  url: http://burtleburtle.net/bob/rand/isaacafa.html
>  (ISAAC's algorithm has been slightly modified in a following paper [4])
> 
>  Those are CSPRNG, yes. Beside the big state required and the relative 
> slowness
>  of those algorithms the only downside I see in using one of those
>  "heavy handed" algorithms is that being stream-based we'd have to implement
>  some buffer-juggling to squeeze a single fixnum out of it.
>  ChaCha20 is what OpenBSD uses for their `arc4random` [3] and rust's `rand`
>  crate implements both at the time of writing [5].
> 
> * PCG
>  url: http://www.pcg-random.org/
> 
>  This is the new kid on the block as you can probably see by the fancy 
> website,
>  this means it hasn't been thoroughly scrutinized and is not battle tested.
>  Nevertheless its the one that's been already adopted by the Crystal
>  programming language and it seems that the next Go iteration is gonna go that
>  way too [6].
>  This one is pretty fast, has a small state, comes in different "sizes" (32,
>  64, 128) while providing a reasonably good output as seen on the website
>  (how much you can trust the results coming from the implementor is still TBD 
> :)
>  and as shown by Daniel Lemire in his blog [7].
> 
> In the end it's all about choosing an algorithm that's good enough for 99% of
> the cases, trying to cover every use case is not going to cut it. I'm no 
> expert
> so feel free to correct whatever error you may find, my English isn't not
> perfect either so you can be pedantic about that if you want. And please do :)
> 
> Thank you for reading,
> LemonBoy
> 
> [1] http://www.pcg-random.org/posts/bugs-in-splitmix.html
> [2] http://www.pcg-random.org/posts/predictability-party-tricks.html
> [3] http://bxr.su/OpenBSD/lib/libc/crypt/arc4random.c
> [4] https://131002.net/data/papers/Aum06b.pdf
> [5] https://doc.rust-lang.org/rand/rand/index.html
> [6] https://github.com/golang/go/issues/21835
> [7] https://lemire.me/blog/
> 
> _______________________________________________
> Chicken-hackers mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/chicken-hackers