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

[lemonboy]

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/