1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
|
------------------------------------------------------------------------------
--- Library for pseudo-random number generation in Curry.
---
--- 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 sequences
--- generated by the `java.util.Random package`.
---
--- The algorithm is taken from
--- <http://en.wikipedia.org/wiki/Random_number_generation>.
--- There is an assumption that all operations are implicitly
--- executed mod 2^32 (unsigned 32-bit integers) !!!
--- GHC computes between -2^29 and 2^29-1, thus the sequence
--- is NOT as random as one would like.
---
--- m_w = <choose-initializer>; /* must not be zero */
--- m_z = <choose-initializer>; /* must not be zero */
---
--- uint get_random()
--- {
--- m_z = 36969 * (m_z & 65535) + (m_z >> 16);
--- m_w = 18000 * (m_w & 65535) + (m_w >> 16);
--- return (m_z << 16) + m_w; /* 32-bit result */
--- }
---
--- @author Sergio Antoy (with extensions by Michael Hanus)
--- @version February 2016
--- @category algorithm
------------------------------------------------------------------------------
module Random
( nextInt, nextIntRange, nextBoolean, getRandomSeed
, shuffle
) where
import Integer ( abs )
import System ( getCPUTime )
import Time
zfact = 36969
wfact = 18000
two16 = 65536
large = 536870911 -- 2^29 - 1
------------------------------------------------------------------
-- Public Operations
------------------------------------------------------------------
--- Returns a sequence of pseudorandom, integer values.
---
--- @param seed - The seed of the random sequence.
nextInt :: Int -> [Int]
nextInt seed =
let ns = if seed == 0 then 1 else seed
next2 mw mz =
let mza = zfact * (mz `mod` two16) + (mz * two16)
mwa = wfact * (mw `mod` two16) + (mw * two16)
tmp = (mza `div` two16 + mwa)
res = if tmp < 0 then tmp+large else tmp
in res : next2 mwa mza
in next2 ns ns
--- Returns a pseudorandom sequence of values
--- between 0 (inclusive) and the specified value (exclusive).
---
--- @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
= map (`mod` n) (nextInt seed)
--- Returns a pseudorandom sequence of boolean values.
---
--- @param seed - The seed of the random sequence.
nextBoolean :: Int -> [Bool]
nextBoolean seed = map (/= 0) (nextInt seed)
--- 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+1)) `mod` two16)
--- Computes a random permutation of the given list.
---
--- @param rnd random seed
--- @param l lists to shuffle
--- @return shuffled list
---
shuffle :: Int -> [a] -> [a]
shuffle rnd xs = shuffleWithLen (nextInt rnd) (length xs) xs
shuffleWithLen :: [Int] -> Int -> [a] -> [a]
shuffleWithLen [] _ _ =
error "Internal error in Random.shuffleWithLen"
shuffleWithLen (r:rs) len xs
| len == 0 = []
| otherwise = z : shuffleWithLen rs (len-1) (ys++zs)
where
(ys,z:zs) = splitAt (abs r `mod` len) xs
{- 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)))
-}
|