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 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 |
------------------------------------------------------------------------------ --- 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 :: Int zfact = 36969 wfact :: Int wfact = 18000 two16 :: Int two16 = 65536 large :: Int 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+1)*(s+1)*(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))) -} |