Re: [Sbcl-devel] random number generation in a tight loop

[Christophe R. <cs...@ca...>]

Paul Khuong <pk...@gm...> writes:

> On 9-Mar-09, at 11:55 AM, Christophe Rhodes wrote:
>> If we're actively aiming to make things better, I'd suggest reading
>> more than one 32-bit value from the entropy pool to improve the number
>> of possible seed values.  Otherwise we're only a short e-mail
>> conversation away from someone complaining that when they generate
>> 65536 random states, two of them give the same random number stream...
>
> But then again, if you need that many random states, and are really  
> worried about similarity or correlation, you probably should be using  
> a PRNG that offers streams/substreams. Even if your randomly-generated  
> states don't collide, you still have to pray that they will be far  
> enough in the sequence of states, which is just as lossy.

If I have two arbitrary random states of the MT, drawn from a uniform
distribution over all the possible MT states.

  p(state dinstance < x) ~ x * 2^{-19936}

so if I have one (privileged) random state and N others, 

  p(min(state distance) < x) ~ (1 - x * 2^{-19936})^N

for x ~ 2^32, N ~ anything really, do we not still have a vanishingly
small probability that any of the states is anywhere near any of the
others?  Formally things don't start getting bad until Nx is
approaching 2^{19900}, even if you are awake enough to do the
calculation of the order statistics properly and not simply choose a
privileged random state?

> For simulation purposes the interface CL (and most other standard  
> libraries) offers is obviously inadequate and shouldn't/couldn't be  
> used for anything but the most basic tasks.

So shouldn't we be providing an extension for seeding a good
simulation-adequate PRNG?  And, while we're at it, a good
cryptographic PRNG (which MT is not...)?

Best,

Christophe