<div dir="ltr">Max,<div>That&#39;s interesting, where can I read about &quot;giant-stepping the generator&quot;?</div><div>The wiki article <a href="http://en.wikipedia.org/wiki/Linear_congruential_generator">http://en.wikipedia.org/wiki/Linear_congruential_generator</a> doesn&#39;t mention distributed processing.</div>
<div>Thanks,</div><div>Peter</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Aug 21, 2013 at 2:44 PM, Max R. Dechantsreiter <span dir="ltr">&lt;<a href="mailto:max@performancejones.com" target="_blank">max@performancejones.com</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Peter,<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
What about the old random number generator: take a 16 bit seed, square it,<br>
take the middle 16 bits, and repeat. They&#39;d want a large number in order<br>
(so you can repeat an experiment, or a run of a model, with the same<br>
&quot;random&quot; numbers), and it&#39;s easy to computer sequentially; but if you want<br>
a million of them it would be nice to distribute the job, but I don&#39;t think<br>
you can. But maybe &quot;can&#39;t parallelize&quot; isn&#39;t the same as &quot;badly inefficient<br>
to parallelize&quot;.<br>
</blockquote>
<br></div>
Many RNG _can_ be distributed.  The enabling characteristic<br>
is the existence of a way to &quot;giant-step&quot; the generator.<br>
This is certainly possible for LCG (LCRNG), such as the one<br>
used throughout NPB I.<br>
<br>
The NPB generator has the form<br>
<br>
         x(k+1) = a*x(k) modulo 2**46 (suggested a = 5**13)<br>
<br>
which has period 2**44.<br>
<br>
It could be an interesting excercise: take two generators,<br>
one which can be distributed, one which cannot....<br>
<br>
Cheers,<br>
<br>
Max<br>
</blockquote></div><br></div>