1 % ------------------------------------------------------------------------------
2 % $Id: Random.lhs,v 1.25 2001/08/29 10:49:28 simonmar Exp $
4 % (c) The University of Glasgow, 1995-2000
7 \section[Random]{Module @Random@}
9 The June 1988 (v31 #6) issue of the Communications of the ACM has an
10 article by Pierre L'Ecuyer called, "Efficient and Portable Combined
11 Random Number Generators". Here is the Portable Combined Generator of
12 L'Ecuyer for 32-bit computers. It has a period of roughly 2.30584e18.
14 Transliterator: Lennart Augustsson
16 sof 1/99 - code brought (kicking and screaming) into the new Random
22 RandomGen(next, split, genRange)
25 , Random ( random, randomR,
35 import PrelGHC ( RealWorld )
36 import PrelShow ( showSignedInt, showSpace )
37 import PrelRead ( readDec )
38 import PrelIOBase ( unsafePerformIO, stToIO )
39 import PrelArr ( STRef, newSTRef, readSTRef, writeSTRef )
40 import Time ( getClockTime, ClockTime(..) )
42 import PrelPrim ( IORef
50 import CPUTime ( getCPUTime )
51 import Char ( isSpace, chr, ord )
55 class RandomGen g where
58 genRange :: g -> (Int,Int)
61 genRange g = (minBound,maxBound)
67 instance RandomGen StdGen where
72 instance Show StdGen where
73 showsPrec p (StdGen s1 s2) =
78 instance Show StdGen where
79 showsPrec p (StdGen s1 s2) =
85 instance Read StdGen where
89 _ -> [stdFromString r] -- because it shouldn't ever fail.
92 (s1, r1) <- readDec (dropWhile isSpace r)
93 (s2, r2) <- readDec (dropWhile isSpace r1)
94 return (StdGen s1 s2, r2)
97 If we cannot unravel the StdGen from a string, create
98 one based on the string given.
100 stdFromString :: String -> (StdGen, String)
101 stdFromString s = (mkStdGen num, rest)
102 where (cs, rest) = splitAt 6 s
103 num = foldl (\a x -> x + 3 * a) 1 (map ord cs)
107 mkStdGen :: Int -> StdGen -- why not Integer ?
109 | s < 0 = mkStdGen (-s)
110 | otherwise = StdGen (s1+1) (s2+1)
112 (q, s1) = s `divMod` 2147483562
113 s2 = q `mod` 2147483398
115 createStdGen :: Integer -> StdGen
117 | s < 0 = createStdGen (-s)
118 | otherwise = StdGen (fromInteger (s1+1)) (fromInteger (s2+1))
120 (q, s1) = s `divMod` 2147483562
121 s2 = q `mod` 2147483398
125 The class definition - see library report for details.
129 -- Minimal complete definition: random and randomR
130 random :: RandomGen g => g -> (a, g)
131 randomR :: RandomGen g => (a,a) -> g -> (a,g)
133 randoms :: RandomGen g => g -> [a]
134 randoms g = x : randoms g' where (x,g') = random g
136 randomRs :: RandomGen g => (a,a) -> g -> [a]
137 randomRs ival g = x : randomRs ival g' where (x,g') = randomR ival g
140 randomIO = getStdRandom random
142 randomRIO :: (a,a) -> IO a
143 randomRIO range = getStdRandom (randomR range)
147 instance Random Int where
148 randomR (a,b) g = randomIvalInteger (toInteger a, toInteger b) g
149 random g = randomR (minBound,maxBound) g
151 instance Random Char where
153 case (randomIvalInteger (toInteger (ord a), toInteger (ord b)) g) of
155 random g = randomR (minBound,maxBound) g
157 instance Random Bool where
159 case (randomIvalInteger (toInteger (bool2Int a), toInteger (bool2Int b)) g) of
160 (x, g) -> (int2Bool x, g)
168 random g = randomR (minBound,maxBound) g
170 instance Random Integer where
171 randomR ival g = randomIvalInteger ival g
172 random g = randomR (toInteger (minBound::Int), toInteger (maxBound::Int)) g
174 instance Random Double where
175 randomR ival g = randomIvalDouble ival id g
176 random g = randomR (0::Double,1) g
178 -- hah, so you thought you were saving cycles by using Float?
179 instance Random Float where
180 random g = randomIvalDouble (0::Double,1) realToFrac g
181 randomR (a,b) g = randomIvalDouble (realToFrac a, realToFrac b) realToFrac g
187 mkStdRNG :: Integer -> IO StdGen
190 return (createStdGen (ct + o))
192 mkStdRNG :: Integer -> IO StdGen
195 (TOD sec _) <- getClockTime
196 return (createStdGen (sec * 12345 + ct + o))
199 randomIvalInteger :: (RandomGen g, Num a) => (Integer, Integer) -> g -> (a, g)
200 randomIvalInteger (l,h) rng
201 | l > h = randomIvalInteger (h,l) rng
202 | otherwise = case (f n 1 rng) of (v, rng') -> (fromInteger (l + v `mod` k), rng')
213 f (n-1) (fromIntegral x + acc * b) g'
215 randomIvalDouble :: (RandomGen g, Fractional a) => (Double, Double) -> (Double -> a) -> g -> (a, g)
216 randomIvalDouble (l,h) fromDouble rng
217 | l > h = randomIvalDouble (h,l) fromDouble rng
219 case (randomIvalInteger (toInteger (minBound::Int), toInteger (maxBound::Int)) rng) of
223 fromDouble ((l+h)/2) +
224 fromDouble ((h-l) / realToFrac intRange) *
225 fromIntegral (x::Int)
230 intRange = toInteger (maxBound::Int) - toInteger (minBound::Int)
232 iLogBase :: Integer -> Integer -> Integer
233 iLogBase b i = if i < b then 1 else 1 + iLogBase b (i `div` b)
235 stdNext :: StdGen -> (Int, StdGen)
236 stdNext (StdGen s1 s2) = (z', StdGen s1'' s2'')
237 where z' = if z < 1 then z + 2147483562 else z
241 s1' = 40014 * (s1 - k * 53668) - k * 12211
242 s1'' = if s1' < 0 then s1' + 2147483563 else s1'
245 s2' = 40692 * (s2 - k' * 52774) - k' * 3791
246 s2'' = if s2' < 0 then s2' + 2147483399 else s2'
248 stdSplit :: StdGen -> (StdGen, StdGen)
249 stdSplit std@(StdGen s1 s2)
252 -- no statistical foundation for this!
253 left = StdGen new_s1 t2
254 right = StdGen t1 new_s2
256 new_s1 | s1 == 2147483562 = 1
259 new_s2 | s2 == 1 = 2147483398
262 StdGen t1 t2 = snd (next std)
269 setStdGen :: StdGen -> IO ()
270 setStdGen sgen = writeIORef theStdGen sgen
272 getStdGen :: IO StdGen
273 getStdGen = readIORef theStdGen
275 theStdGen :: IORef StdGen
276 theStdGen = unsafePerformIO (newIORef (createStdGen 0))
280 global_rng :: STRef RealWorld StdGen
281 global_rng = unsafePerformIO $ do
283 stToIO (newSTRef rng)
285 setStdGen :: StdGen -> IO ()
286 setStdGen sgen = stToIO (writeSTRef global_rng sgen)
288 getStdGen :: IO StdGen
289 getStdGen = stToIO (readSTRef global_rng)
294 newStdGen :: IO StdGen
297 let (a,b) = split rng
301 getStdRandom :: (StdGen -> (a,StdGen)) -> IO a
304 let (v, new_rng) = f rng