<div class="gmail_quote">2009/2/26 James Swaine <span dir="ltr">&lt;<a href="mailto:james.swaine@gmail.com">james.swaine@gmail.com</a>&gt;</span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
--gets r[k], which is the value at the kth <br>--position in the overall sequence of <br>


--pseudorandom numbers <br>getRandAt :: Int64 -&gt; Int64 -&gt; Float <br>getRandAt 0 seed = multiplier * (fromIntegral seed) <br>getRandAt k seed = multiplier * (fromIntegral x_next) <br>    where <br>        x_prev = (a^k * seed) `mod` divisor<br>



        x_next = (a * x_prev) `mod` divisor</blockquote><div><br></div><div>One thing that comes to mind is that this exponentiation, with a very big exponent, could potentially take a very long time. I believe that GHC implements (^) using a repeated squaring technique, so it runs in log(k) time, which ought to be no problem.  I&#39;m not sure about other compilers though.</div>
<div><br></div><div>Also note:</div><div><br></div><div>(a^k * seed) `mod` divisor = ((a^k `mod` divisor) * seed) `mod` divisor = (a^(k `mod` phi(divisor)) * seed) `mod` divisor.</div><div><br></div><div>Where phi is the Euler totient function: phi(2^46) = 2^23.</div>
<div><br></div><div>Modulo errors... it&#39;s been a while since I&#39;ve done this stuff.</div><div><br></div><div>Luke</div></div>