1 -----------------------------------------------------------------------------
3 -- Module : System.Random
4 -- Copyright : (c) The University of Glasgow 2001
5 -- License : BSD-style (see the file libraries/base/LICENSE)
7 -- Maintainer : libraries@haskell.org
8 -- Stability : provisional
9 -- Portability : portable
13 -----------------------------------------------------------------------------
20 -- * The 'RandomGen' class, and the 'StdGen' generator
22 RandomGen(next, split, genRange)
26 -- * The 'Random' class
27 , Random ( random, randomR,
31 -- * The global random number generator
47 import System.CPUTime ( getCPUTime )
48 import Data.Char ( isSpace, chr, ord )
49 import System.IO.Unsafe ( unsafePerformIO )
51 import Numeric ( readDec )
53 #ifdef __GLASGOW_HASKELL__
54 import GHC.IOBase ( stToIO )
55 import System.Time ( getClockTime, ClockTime(..) )
60 The "Random" library deals with the common task of pseudo-random
61 number generation. The library makes it possible to generate
62 repeatable results, by starting with a specified initial random
63 number generator; or to get different results on each run by using the
64 system-initialised generator, or by supplying a seed from some other
67 The library is split into two layers:
69 * A core /random number generator/ provides a supply of bits. The class
70 'RandomGen' provides a common interface to such generators.
72 * The class 'Random' provides a way to extract particular values from
73 a random number generator. For example, the 'Float' instance of 'Random'
74 allows one to generate random values of type 'Float'.
76 [Comment found in this file when merging with Library Report:]
78 The June 1988 (v31 \#6) issue of the Communications of the ACM has an
79 article by Pierre L'Ecuyer called, /Efficient and Portable Combined
80 Random Number Generators/. Here is the Portable Combined Generator of
81 L'Ecuyer for 32-bit computers. It has a period of roughly 2.30584e18.
83 Transliterator: Lennart Augustsson
88 -- The class 'RandomGen' provides a common interface to random number generators.
90 class RandomGen g where
92 -- |The 'next' operation allows one to extract at least 30 bits (one 'Int''s
93 -- worth) from the generator, returning a new generator as well. The
94 -- integer returned may be positive or negative.
97 -- |The 'split' operation allows one to obtain two distinct random number
98 -- generators. This is very useful in functional programs (for example, when
99 -- passing a random number generator down to recursive calls), but very
100 -- little work has been done on statistically robust implementations of
101 -- @split ([1,4]@ are the only examples we know of).
104 genRange :: g -> (Int,Int)
107 genRange g = (minBound,maxBound)
109 {- |The "Random" library provides one instance of 'RandomGen', the abstract data
112 The result of repeatedly using next should be at least as statistically robust
113 as the /Minimal Standard Random Number Generator/ described by
114 ["System.Random\#Park", "System.Random\#Carta"]. Until more
115 is known about implementations of 'split', all we require is that 'split' deliver
116 generators that are (a) not identical and (b) independently robust in the sense
119 The 'show'\/'Read' instances of 'StdGen' provide a primitive way to save the
120 state of a random number generator. It is required that @read (show g) == g@.
122 In addition, 'read' may be used to map an arbitrary string (not necessarily one
123 produced by 'show') onto a value of type 'StdGen'. In general, the 'read'
124 instance of 'StdGen' has the following properties:
126 * It guarantees to succeed on any string.
128 *It guarantees to consume only a finite portion of the string.
130 * Different argument strings are likely to result in different results.
132 The function 'mkStdGen' provides an alternative way of producing an initial
133 generator, by mapping an 'Int' into a generator. Again, distinct arguments
134 should be likely to produce distinct generators.
136 Programmers may, of course, supply their own instances of 'RandomGen'.
143 instance RandomGen StdGen where
147 instance Show StdGen where
148 showsPrec p (StdGen s1 s2) =
153 instance Read StdGen where
154 readsPrec _p = \ r ->
157 _ -> [stdFromString r] -- because it shouldn't ever fail.
160 (s1, r1) <- readDec (dropWhile isSpace r)
161 (s2, r2) <- readDec (dropWhile isSpace r1)
162 return (StdGen s1 s2, r2)
165 If we cannot unravel the StdGen from a string, create
166 one based on the string given.
168 stdFromString :: String -> (StdGen, String)
169 stdFromString s = (mkStdGen num, rest)
170 where (cs, rest) = splitAt 6 s
171 num = foldl (\a x -> x + 3 * a) 1 (map ord cs)
174 mkStdGen :: Int -> StdGen -- why not Integer ?
176 | s < 0 = mkStdGen (-s)
177 | otherwise = StdGen (s1+1) (s2+1)
179 (q, s1) = s `divMod` 2147483562
180 s2 = q `mod` 2147483398
182 createStdGen :: Integer -> StdGen
184 | s < 0 = createStdGen (-s)
185 | otherwise = StdGen (fromInteger (s1+1)) (fromInteger (s2+1))
187 (q, s1) = s `divMod` 2147483562
188 s2 = q `mod` 2147483398
190 -- FIXME: 1/2/3 below should be ** (vs@30082002) XXX
192 {- |The 'Random' class
193 With a source of random number supply in hand, the 'Random' class allows the
194 programmer to extract random values of a variety of types.
196 * 'randomR' takes a range /(lo,hi)/ and a random number generator /g/, and returns
197 a random value uniformly distributed in the closed interval /[lo,hi]/, together
198 with a new generator. It is unspecified what happens if /lo>hi/. For continuous
199 types there is no requirement that the values /lo/ and /hi/ are ever produced,
200 but they may be, depending on the implementation and the interval.
202 * 'random' does the same as 'randomR', but does not take a range.
204 (1) For bounded types (instances of 'Bounded', such as 'Char'), the range is
205 normally the whole type.
207 (2) For fractional types, the range is normally the semi-closed interval @[0,1)@.
209 (3) For 'Integer', the range is (arbitrarily) the range of 'Int'.
211 * The plural versions, 'randomRs' and 'randoms', produce an infinite list of
212 random values, and do not return a new generator.
214 * The 'IO' versions, 'randomRIO' and 'randomIO', use the global random number
215 generator (see Section 17.3
216 <http://www.haskell.org/onlinelibrary/random.html#global-rng>).
220 -- |Minimal complete definition: 'random' and 'randomR'
221 random :: RandomGen g => g -> (a, g)
222 randomR :: RandomGen g => (a,a) -> g -> (a,g)
225 randoms :: RandomGen g => g -> [a]
226 randoms g = x : randoms g' where (x,g') = random g
228 randomRs :: RandomGen g => (a,a) -> g -> [a]
229 randomRs ival g = x : randomRs ival g' where (x,g') = randomR ival g
232 randomIO = getStdRandom random
234 randomRIO :: (a,a) -> IO a
235 randomRIO range = getStdRandom (randomR range)
238 instance Random Int where
239 randomR (a,b) g = randomIvalInteger (toInteger a, toInteger b) g
240 random g = randomR (minBound,maxBound) g
242 instance Random Char where
244 case (randomIvalInteger (toInteger (ord a), toInteger (ord b)) g) of
246 random g = randomR (minBound,maxBound) g
248 instance Random Bool where
250 case (randomIvalInteger (toInteger (bool2Int a), toInteger (bool2Int b)) g) of
251 (x, g) -> (int2Bool x, g)
259 random g = randomR (minBound,maxBound) g
261 instance Random Integer where
262 randomR ival g = randomIvalInteger ival g
263 random g = randomR (toInteger (minBound::Int), toInteger (maxBound::Int)) g
265 instance Random Double where
266 randomR ival g = randomIvalDouble ival id g
267 random g = randomR (0::Double,1) g
269 -- hah, so you thought you were saving cycles by using Float?
270 instance Random Float where
271 random g = randomIvalDouble (0::Double,1) realToFrac g
272 randomR (a,b) g = randomIvalDouble (realToFrac a, realToFrac b) realToFrac g
274 #ifdef __GLASGOW_HASKELL__
275 mkStdRNG :: Integer -> IO StdGen
278 (TOD sec _) <- getClockTime
279 return (createStdGen (sec * 12345 + ct + o))
283 mkStdRNG :: Integer -> IO StdGen
286 return (createStdGen (ct + o))
289 randomIvalInteger :: (RandomGen g, Num a) => (Integer, Integer) -> g -> (a, g)
290 randomIvalInteger (l,h) rng
291 | l > h = randomIvalInteger (h,l) rng
292 | otherwise = case (f n 1 rng) of (v, rng') -> (fromInteger (l + v `mod` k), rng')
303 f (n-1) (fromIntegral x + acc * b) g'
305 randomIvalDouble :: (RandomGen g, Fractional a) => (Double, Double) -> (Double -> a) -> g -> (a, g)
306 randomIvalDouble (l,h) fromDouble rng
307 | l > h = randomIvalDouble (h,l) fromDouble rng
309 case (randomIvalInteger (toInteger (minBound::Int), toInteger (maxBound::Int)) rng) of
313 fromDouble ((l+h)/2) +
314 fromDouble ((h-l) / realToFrac intRange) *
315 fromIntegral (x::Int)
320 intRange = toInteger (maxBound::Int) - toInteger (minBound::Int)
322 iLogBase :: Integer -> Integer -> Integer
323 iLogBase b i = if i < b then 1 else 1 + iLogBase b (i `div` b)
325 stdNext :: StdGen -> (Int, StdGen)
326 stdNext (StdGen s1 s2) = (z', StdGen s1'' s2'')
327 where z' = if z < 1 then z + 2147483562 else z
331 s1' = 40014 * (s1 - k * 53668) - k * 12211
332 s1'' = if s1' < 0 then s1' + 2147483563 else s1'
335 s2' = 40692 * (s2 - k' * 52774) - k' * 3791
336 s2'' = if s2' < 0 then s2' + 2147483399 else s2'
338 stdSplit :: StdGen -> (StdGen, StdGen)
339 stdSplit std@(StdGen s1 s2)
342 -- no statistical foundation for this!
343 left = StdGen new_s1 t2
344 right = StdGen t1 new_s2
346 new_s1 | s1 == 2147483562 = 1
349 new_s2 | s2 == 1 = 2147483398
352 StdGen t1 t2 = snd (next std)
354 -- The global random number generator
358 There is a single, implicit, global random number generator of type
359 'StdGen', held in some global variable maintained by the 'IO' monad. It is
360 initialised automatically in some system-dependent fashion, for example, by
361 using the time of day, or Linux's kernel random number generator. To get
362 deterministic behaviour, use 'setStdGen'.
365 -- |'setStdGen' sets the global random number generator.
366 setStdGen :: StdGen -> IO ()
367 setStdGen sgen = writeIORef theStdGen sgen
369 -- |'getStdGen' gets the global random number generator.
370 getStdGen :: IO StdGen
371 getStdGen = readIORef theStdGen
373 -- |'newStdGen' applies 'split' to the current global random generator, updates it
374 -- with one of the results, and returns the other.
375 theStdGen :: IORef StdGen
376 theStdGen = unsafePerformIO $ do
380 newStdGen :: IO StdGen
383 let (a,b) = split rng
387 {- |'getStdRandom' uses the supplied function to get a value from the current
388 global random generator, and updates the global generator with the new generator
389 returned by the function. For example, 'rollDice' gets a random integer between 1 and 6:
392 > rollDice = getStdRandom (randomR (1,6))
396 getStdRandom :: (StdGen -> (a,StdGen)) -> IO a
399 let (v, new_rng) = f rng
405 * [1] FW Burton and RL Page, /Distributed random number generation/,
406 Journal of Functional Programming, 2(2):203-212, April 1992.
408 * [2] SK #Park# Park, and KW Miller, /Random number generators -
409 good ones are hard to find/, Comm ACM 31(10), Oct 1988, pp1192-1201.
411 * [3] DG #Carta# Carta, /Two fast implementations of the minimal standard
412 random number generator/, Comm ACM, 33(1), Jan 1990, pp87-88.
414 * [4] P Hellekalek, /Don\'t trust parallel Monte Carlo/,
415 Department of Mathematics, University of Salzburg,
416 <http://random.mat.sbg.ac.at/~peter/pads98.ps>, 1998.
418 The Web site <http://random.mat.sbg.ac.at/> is a great source of information.