osdir.com


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

on the prng behind random.random()


Dennis Lee Bieber <wlfraed at ix.netcom.com> writes:

> On Mon, 19 Nov 2018 19:05:44 -0200, Robert Girault <r at dev.null> declaimed
> the following:
>
>>I mean the fact that with 624 samples from the generator, you can
>>determine the rest of the sequence completely.
>
> 	Being able to predict the sequence after a large sampling does not mean
> that the /distribution of values/ is not (pseudo-) random.

The problem with determining its sequence is that it might defeat its
purpose.  If you use mt19937 to select a pivot in random Quicksort for
example (where you plan to spend n lg n time in sorting), we can
frustrate your plans and force it into n^2 every time, an effective DoS
attack on your software.

> 	After all, pretty much all random number generators will produce the
> same sequence if given the same starting seed... You are, in effect,
> treating your 624 samples as a very large seed...

I think I disagree with your take here.  With mt19937, given ANY seed, I
can eventually predict all the sequence without having to query the
oracle any further.

If you're just writing a toy software, even K&R PRNG works just fine.
If you're writing a weather simulation, I suppose you need real
random-like properties and still need your generator to be reproducible.
If you're using random Quicksort, you do need unpredictability and
reproducibility.  If you're writing a crypto application, then you need
something way stronger.  We need all of them.  But mt19937 is now useful
only in toy software.