[Haskell-cafe] Performance Issue

[Luke Palmer]

2009/2/26 James Swaine <james.swaine at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090226/49b0e33c/attachment.htm