[m-rev.] RNGs

[Julien Fischer]

Hi Mark,

On Mon, 19 Aug 2019, Mark Brown wrote:

> On Mon, Aug 19, 2019 at 1:48 PM Julien Fischer <jfischer at opturion.com> wrote:
>>
>> On Mon, 19 Aug 2019, Mark Brown wrote:
>>
>>> On Mon, Aug 19, 2019 at 1:45 AM 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.
>
> Ok. I'll take that to mean that marsaglia and tausworthe can be put in extras.

Yep.

...

>>>>
>>>> I think the basic unit returned by an RNG ought to be a uint32 rather than a
>>>> uint64 -- I note most of the implementations you have here actually do that
>>>> anyway and just cast the result to a uint64.
>>>
>>> What's the advantage of uint32?
>>
>> We still support 32-bit platforms; even if you say native 32-bit
>> platforms are unimportant now, that still leaves things like the JVM.
>> It's essentially the lowest common denominator type here.  What's the
>> advantage of uint64 for this?
>
> I'm not sure I understand the objection. Uint64 still works on 32-bit
> platforms, doesn't it?

Yes.

> it is just less efficient?

Potentially, they may be boxed (in C grades).

> The advantage of uint64 is that it only takes one method call to get
> 64-bits of information out of a generator, instead of two.

True, although in many cases you are not going to need 64-bits of
randomness.

> At the speed these things work that is noticeably faster, I think, and
> I'd rather sacrifice performance on JVM than here.

That's a fair point, and probably doesn't reflect well on the compiler's
to specialise method calls.

An alternative would be for each generator to export methods for
generating each fixed size unsigned integer types.  That is, add the
following to the type class(es):

     next_uint8
     next_uint16
     next_uint32
     next_uint64

That seems more flexible and uniform so far as callers are concerned, if
a little more work for implementors.

>>>> I suggest we impose a stronger requirement on RNGs here, namely that each
>>>> call to random/3 returns a random 64-bit (or 32-bit) word.  It is the
>>>> responsbility of the RNG instance to fulfil that requirement.   Most modern
>>>> pseudo-random number generators should be fine with this requirement.
>>>
>>> I've documented that the numbers should be uniformly distributed,
>>> although this implies most instances will only be pseudo-correct ;-)
>>
>> <https://dilbert.com/strip/2001-10-25>
>
> I picked "default" seeds for sfc using "hexdump -Cv /dev/urandom |
> head". Go figure.
>
>>
>>> I've also added that random_max should be no less than 65535, as it
>>> doesn't seem too much to ask instances to be able to come up with at
>>> least 16 bits at a time.
>>
>> Imposing the stronger requirement I gave above should simplify code that
>> uses the RNG because it won't have to concern itself with how much of
>> the output is actually random.  Under that requirement a 16-bit RNG
>> would just have to combine multiple outputs until it reaches the
>> required number of random bits.
>
> Oh, I see what you mean. That would mean there would be no need for
> the random_max methods, right?

Correct.

> That would cut down on method calls, and I agree that most modern
> generators will be fine with this.

Modern generators typically generate a 32- or 64-bit word of random
bits.  I don't think it's worth putting in too much effort to accomodate
older generators, they tend to be defective anyway.

Julien.