On Tuesday, 19 January 2016 at 00:02:08 UTC, Timon Gehr wrote:
On 01/19/2016 12:55 AM, Ilya wrote:
On Monday, 18 January 2016 at 23:53:53 UTC, Timon Gehr wrote:
On 01/19/2016 12:50 AM, Ilya wrote:
...
1. Yes, probability of hitting the worst case repeatedly is
is
practically zero. But RNGs do not change this probability.
2. It is possible to build attack for our RNGs, because they
are
Pseudo-RNGs.
--Ilya
You also need to predict the seed. How do you do that?
We can not use unpredictable seed (like system clock) in pure
functions.
--Ilya
Clearly. The point is, there already was an impure
implementation of topN whose expected linear running time is
still specified in the documentation. The current
implementation does not fulfill this bound.
There is already implementation with predictable seed. Proof:
https://github.com/D-Programming-Language/phobos/blob/master/std/random.d#L1151 --Ilya
