[m-rev.] RNGs

[Julien Fischer]

Hi Mark,

On Sun, 25 Aug 2019, Mark Brown wrote:

> 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.

That's reasonable.

> 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.)

I think that's sufficent for the standard library; as I mentioned earlier
in this thread, any other generators can go in extras.

Julien.