--- This library provides operations for generating pseudo-random --- number sequences. --- For any given seed, the sequences generated by the operations --- in this module should be identical to the sequnces --- generated by the java.util.Random package. ---
--- The algorithm is a linear congruential pseudo-random number generator
--- described in Donald E. Knuth, The
--- Art of Computer Programming, Volume 2: Seminumerical
--- Algorithms, section 3.2.1.
---
--- @author Sergio Antoy (with extensions by Michael Hanus)
--- @version December 2004
------------------------------------------------------------------------------
module Random(nextInt, nextIntRange, nextBoolean, getRandomSeed) where
import Time
import System(getCPUTime)
------------------------------------------------------------------
-- Private Operations
------------------------------------------------------------------
-- a few constants
multiplier = 25214903917
addend = 11
powermask = 48
mask = 281474976710656 -- 2^powermask
intsize = 32
intspan = 4294967296 -- 2^intsize
intlimit = 2147483648 -- 2^(intsize-1)
-- the basic sequence of random values
sequence seed = next : sequence next
where next = nextseed seed
-- auxiliary private operations
nextseed seed = (seed * multiplier + addend) `mod` mask
xor x y = if (x==0) && (y==0) then 0 else lastBit + 2 * restBits
where lastBit = if (x `mod` 2) == (y `mod` 2) then 0 else 1
restBits = xor (x `div` 2) (y `div` 2)
power base exp = binary 1 base exp
where binary x b e
= if (e == 0) then x
else binary (x * if (e `mod` 2 == 1) then b else 1)
(b * b)
(e `div` 2)
nextIntBits seed bits = map adjust list
where init = (xor seed multiplier) `mod` mask
list = sequence init
shift = power 2 (powermask - bits)
adjust x = if arg > intlimit then arg - intspan
else arg
where arg = (x `div` shift) `mod` intspan
------------------------------------------------------------------
-- Public Operations
------------------------------------------------------------------
--- Returns a sequence of pseudorandom, uniformly distributed 32-bits
--- integer values. All 232
--- possible integer values are produced with
--- (approximately) equal probability.
---
--- @param seed - The seed of the random sequence.
nextInt :: Int -> [Int]
nextInt seed = nextIntBits seed intsize
--- Returns a pseudorandom, uniformly distributed sequence of values
--- between 0 (inclusive) and the specified value (exclusive).
--- Each value is a 32-bits positive integer.
--- All n possible values are produced with (approximately) equal
--- probability.
--- @param seed - The seed of the random sequence.
--- @param n - The bound on the random number to be returned.
--- Must be positive.
nextIntRange :: Int -> Int -> [Int]
nextIntRange seed n | n>0
= if power_of_2 n then map adjust_a seq
else map adjust_b (filter adjust_c seq)
where seq = nextIntBits seed (intsize - 1)
adjust_a x = (n * x) `div` intlimit
adjust_b x = x `mod` n
adjust_c x = x - (x `mod` n) + (n - 1) >= 0
power_of_2 k = k == 2 ||
k > 2 && k `mod` 2 == 0 && power_of_2 (k `div` 2)
--- Returns a pseudorandom, uniformly distributed sequence of
--- boolean values. The
--- values True and False are produced with
--- (approximately) equal probability.
--- @param seed - The seed of the random sequence.
nextBoolean :: Int -> [Bool]
nextBoolean seed = map (/= 0) (nextIntBits seed 1)
--- Returns a time-dependent integer number as a seed for really random numbers.
--- Should only be used as a seed for pseudorandom number sequence
--- and not as a random number since the precision is limited to milliseconds
getRandomSeed :: IO Int
getRandomSeed =
getClockTime >>= \time ->
getCPUTime >>= \msecs ->
let (CalendarTime y mo d h m s _) = toUTCTime time
in return ((y+mo+d+h+m*s*msecs) `mod` mask)
{- Simple tests and examples
testInt = take 20 (nextInt 0)
testIntRange = take 120 (nextIntRange 0 6)
testBoolean = take 20 (nextBoolean 0)
reallyRandom = do seed <- getRandomSeed
putStrLn (show (take 20 (nextIntRange seed 100)))
-}