[m-rev.] RNGs

[Mark Brown]

On Mon, Aug 19, 2019 at 1:48 PM Julien Fischer <jfischer at opturion.com> wrote:
> As I mentioned above, extra RNGs can live in extras.  The standard
> library itself only needs to provide a few generators: one that is fast
> and one that is "good" (in the statistically random sense), assuming
> that there is not one that is both.

Let me know if you see any flaws in the following argument.

In order to be fast, a generator needs to avoid allocating heap when
generating a number. And in order to be good, it needs more than 64
bits of state. We can do both but that requires destructive update and
hence uniqueness, and that means the interface will be less convenient
than for a ground generator.

The upshot of this is that we can choose any two out of fast, good and
convenient. Considering that whether heap is needed will depend on the
word size, that gives us six use cases. Generators satisfying these
cases are:

64-bit, fast, good: unique 64-bit sfc
64-bit, convenient, good: shared 32- or 64-bit sfc
64-bit, fast, convenient: shared 16-bit sfc

32-bit, fast, good: unique 32-bit sfc
32-bit, convenient, good: shared 32-bit sfc
32-bit, fast, convenient: marsaglia

So that gives us four generators for the standard library: 16-, 32-
and 64-bit sfc, and marsaglia. (The 'make_shared_rng' adapter is used
to make the shared versions of 32- and 64-bit sfc.)

Mark