<div class="gmail_quote">On Wed, Aug 17, 2011 at 12:27 PM, Ryan Newton <span dir="ltr">&lt;<a href="mailto:rrnewton@gmail.com">rrnewton@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="gmail_quote"><div class="im"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="gmail_quote"><div><div>The more fundamental problem is that splitting is neither well understood nor generally safe, and as such it should not be in the basic Random class.</div>


</div></div></blockquote><div> </div></div><div>Would you mind elaborating?</div></div></blockquote><div><br></div><div>Certainly. The purpose of splitting a PRNG is to create two new PRNGs, with the following properties:</div>
<div><ul><li>Long periods</li><li>The streams generated by each PRNG must be independent</li><li>Splitting must be fast, while preserving the above two properties</li></ul>It&#39;s very easy to write a split function that gets at least one of these considerations wrong.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="gmail_quote"><div>But I am under the impression that it is well understood by Burton Smith and others who have worked on the topic, and that they assure us that using AES, RNG&#39;s under any series of splits are as strong as those generated in a linear sequence.</div>
</div></blockquote><div><br></div><div>The trouble is that very few people have worked on this topic - there&#39;s almost no published literature on it. And Burton and his colleagues readily admit that the technique they suggest is a matter of folk wisdom in the crypto community.</div>
<div><br></div><div>A typical technical application of a PRNG is for Monte Carlo processes, where you want to (a) have a very fast PRNG and (b) understand its properties. Burton&#39;s off-the-cuff suggestion is all very well, but we don&#39;t know important things like what the performance or period of that PRNG would be. For instance, if we don&#39;t know a PRNG&#39;s period, we don&#39;t know when we&#39;re going to start seeing autocorrelations in its output, or if it supports splitting, how many splits are safe to perform before we start seeing <i>cross</i>-stream correlation. This in turn means that we don&#39;t know whether, when, or why the consumers of our pseudo-random numbers are going to themselves start producing garbage results, and that&#39;s troubling to me.</div>
<div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="gmail_quote"><div>Could you expound on this also?  The people I know in the parallelism community seem to care a lot about deterministic PRNG in parallel programs.</div>
</div></blockquote><div><br></div><div>Yep, but don&#39;t conflate determinism with splitting. In the imperative world, you normally know how many CPUs you have, so you initialize one PRNG per CPU, and simply go from there; there&#39;s no need for splitting. In the parallel community, people are going out of their way to <i>avoid</i> splitting.</div>
<div></div></div><br><div>The only good treatments of this subject that I know are published by the SPRNG authors at FSU.</div>