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 140 141 142 143 144 145 146 147 148 149 150 151 152 153
|
------------------------------------------------------------------------------
--- 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 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 February 2016
--- @category algorithm
------------------------------------------------------------------------------
module Random
( nextInt, nextIntRange, nextBoolean, getRandomSeed
, shuffle
) where
import Integer ( abs )
import System ( getCPUTime )
import Time
------------------------------------------------------------------
-- 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 2<font size="-1"><sup>32</sup></font>
--- 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)
--- 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)))
-}
|