2009/2/26 James Swaine <james.swa...@gmail.com> > --gets r[k], which is the value at the kth > --position in the overall sequence of > --pseudorandom numbers > getRandAt :: Int64 -> Int64 -> Float > getRandAt 0 seed = multiplier * (fromIntegral seed) > getRandAt k seed = multiplier * (fromIntegral x_next) > where > x_prev = (a^k * seed) `mod` divisor > x_next = (a * x_prev) `mod` divisor
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'm not sure about other compilers though. Also note: (a^k * seed) `mod` divisor = ((a^k `mod` divisor) * seed) `mod` divisor = (a^(k `mod` phi(divisor)) * seed) `mod` divisor. Where phi is the Euler totient function: phi(2^46) = 2^23. Modulo errors... it's been a while since I've done this stuff. Luke
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe