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
48 import CPUTime ( getCPUTime )
49 import Foreign.Ptr ( Ptr, nullPtr )
51 import System.CPUTime ( getCPUTime )
52 import System.Time ( getClockTime, ClockTime(..) )
54 import Data.Char ( isSpace, chr, ord )
55 import System.IO.Unsafe ( unsafePerformIO )
57 import Numeric ( readDec )
59 -- The standard nhc98 implementation of Time.ClockTime does not match
60 -- the extended one expected in this module, so we lash-up a quick
63 data ClockTime = TOD Integer ()
64 foreign import ccall "time.h time" readtime :: Ptr () -> IO Int
65 getClockTime :: IO ClockTime
66 getClockTime = do t <- readtime nullPtr; return (TOD (toInteger t) ())
71 This library deals with the common task of pseudo-random
72 number generation. The library makes it possible to generate
73 repeatable results, by starting with a specified initial random
74 number generator; or to get different results on each run by using the
75 system-initialised generator, or by supplying a seed from some other
78 The library is split into two layers:
80 * A core /random number generator/ provides a supply of bits. The class
81 'RandomGen' provides a common interface to such generators.
83 * The class 'Random' provides a way to extract particular values from
84 a random number generator. For example, the 'Float' instance of 'Random'
85 allows one to generate random values of type 'Float'.
87 [Comment found in this file when merging with Library Report:]
89 The June 1988 (v31 \#6) issue of the Communications of the ACM has an
90 article by Pierre L'Ecuyer called, /Efficient and Portable Combined
91 Random Number Generators/. Here is the Portable Combined Generator of
92 L'Ecuyer for 32-bit computers. It has a period of roughly 2.30584e18.
94 Transliterator: Lennart Augustsson
99 -- The class 'RandomGen' provides a common interface to random number generators.
101 class RandomGen g where
103 -- |The 'next' operation allows one to extract at least 30 bits (one 'Int''s
104 -- worth) from the generator, returning a new generator as well. The
105 -- integer returned may be positive or negative.
106 next :: g -> (Int, g)
108 -- |The 'split' operation allows one to obtain two distinct random number
109 -- generators. This is very useful in functional programs (for example, when
110 -- passing a random number generator down to recursive calls), but very
111 -- little work has been done on statistically robust implementations of
112 -- @split ([1,4]@ are the only examples we know of).
115 genRange :: g -> (Int,Int)
118 genRange g = (minBound,maxBound)
120 {- |The "System.Random" library provides one instance of 'RandomGen', the
121 abstract data type 'StdGen'.
123 The result of repeatedly using next should be at least as statistically robust
124 as the /Minimal Standard Random Number Generator/ described by
125 ["System.Random\#Park", "System.Random\#Carta"]. Until more
126 is known about implementations of 'split', all we require is that 'split' deliver
127 generators that are (a) not identical and (b) independently robust in the sense
130 The 'show'\/'Read' instances of 'StdGen' provide a primitive way to save the
131 state of a random number generator. It is required that @read (show g) == g@.
133 In addition, 'read' may be used to map an arbitrary string (not necessarily one
134 produced by 'show') onto a value of type 'StdGen'. In general, the 'read'
135 instance of 'StdGen' has the following properties:
137 * It guarantees to succeed on any string.
139 *It guarantees to consume only a finite portion of the string.
141 * Different argument strings are likely to result in different results.
143 The function 'mkStdGen' provides an alternative way of producing an initial
144 generator, by mapping an 'Int' into a generator. Again, distinct arguments
145 should be likely to produce distinct generators.
147 Programmers may, of course, supply their own instances of 'RandomGen'.
154 instance RandomGen StdGen where
158 instance Show StdGen where
159 showsPrec p (StdGen s1 s2) =
164 instance Read StdGen where
165 readsPrec _p = \ r ->
168 _ -> [stdFromString r] -- because it shouldn't ever fail.
171 (s1, r1) <- readDec (dropWhile isSpace r)
172 (s2, r2) <- readDec (dropWhile isSpace r1)
173 return (StdGen s1 s2, r2)
176 If we cannot unravel the StdGen from a string, create
177 one based on the string given.
179 stdFromString :: String -> (StdGen, String)
180 stdFromString s = (mkStdGen num, rest)
181 where (cs, rest) = splitAt 6 s
182 num = foldl (\a x -> x + 3 * a) 1 (map ord cs)
185 mkStdGen :: Int -> StdGen -- why not Integer ?
187 | s < 0 = mkStdGen (-s)
188 | otherwise = StdGen (s1+1) (s2+1)
190 (q, s1) = s `divMod` 2147483562
191 s2 = q `mod` 2147483398
193 createStdGen :: Integer -> StdGen
195 | s < 0 = createStdGen (-s)
196 | otherwise = StdGen (fromInteger (s1+1)) (fromInteger (s2+1))
198 (q, s1) = s `divMod` 2147483562
199 s2 = q `mod` 2147483398
201 -- FIXME: 1/2/3 below should be ** (vs@30082002) XXX
203 {- |The 'Random' class
204 With a source of random number supply in hand, the 'Random' class allows the
205 programmer to extract random values of a variety of types.
207 * 'randomR' takes a range /(lo,hi)/ and a random number generator /g/, and returns
208 a random value uniformly distributed in the closed interval /[lo,hi]/, together
209 with a new generator. It is unspecified what happens if /lo>hi/. For continuous
210 types there is no requirement that the values /lo/ and /hi/ are ever produced,
211 but they may be, depending on the implementation and the interval.
213 * 'random' does the same as 'randomR', but does not take a range.
215 (1) For bounded types (instances of 'Bounded', such as 'Char'), the range is
216 normally the whole type.
218 (2) For fractional types, the range is normally the semi-closed interval @[0,1)@.
220 (3) For 'Integer', the range is (arbitrarily) the range of 'Int'.
222 * The plural versions, 'randomRs' and 'randoms', produce an infinite list of
223 random values, and do not return a new generator.
225 * The 'IO' versions, 'randomRIO' and 'randomIO', use the global random number
226 generator (see Section 17.3
227 <http://www.haskell.org/onlinelibrary/random.html#global-rng>).
231 -- |Minimal complete definition: 'random' and 'randomR'
232 random :: RandomGen g => g -> (a, g)
233 randomR :: RandomGen g => (a,a) -> g -> (a,g)
236 randoms :: RandomGen g => g -> [a]
237 randoms g = (\(x,g') -> x : randoms g') (random g)
239 randomRs :: RandomGen g => (a,a) -> g -> [a]
240 randomRs ival g = x : randomRs ival g' where (x,g') = randomR ival g
243 randomIO = getStdRandom random
245 randomRIO :: (a,a) -> IO a
246 randomRIO range = getStdRandom (randomR range)
249 instance Random Int where
250 randomR (a,b) g = randomIvalInteger (toInteger a, toInteger b) g
251 random g = randomR (minBound,maxBound) g
253 instance Random Char where
255 case (randomIvalInteger (toInteger (ord a), toInteger (ord b)) g) of
257 random g = randomR (minBound,maxBound) g
259 instance Random Bool where
261 case (randomIvalInteger (toInteger (bool2Int a), toInteger (bool2Int b)) g) of
262 (x, g) -> (int2Bool x, g)
270 random g = randomR (minBound,maxBound) g
272 instance Random Integer where
273 randomR ival g = randomIvalInteger ival g
274 random g = randomR (toInteger (minBound::Int), toInteger (maxBound::Int)) g
276 instance Random Double where
277 randomR ival g = randomIvalDouble ival id g
278 random g = randomR (0::Double,1) g
280 -- hah, so you thought you were saving cycles by using Float?
281 instance Random Float where
282 random g = randomIvalDouble (0::Double,1) realToFrac g
283 randomR (a,b) g = randomIvalDouble (realToFrac a, realToFrac b) realToFrac g
285 mkStdRNG :: Integer -> IO StdGen
288 (TOD sec _) <- getClockTime
289 return (createStdGen (sec * 12345 + ct + o))
291 randomIvalInteger :: (RandomGen g, Num a) => (Integer, Integer) -> g -> (a, g)
292 randomIvalInteger (l,h) rng
293 | l > h = randomIvalInteger (h,l) rng
294 | otherwise = case (f n 1 rng) of (v, rng') -> (fromInteger (l + v `mod` k), rng')
305 f (n-1) (fromIntegral x + acc * b) g'
307 randomIvalDouble :: (RandomGen g, Fractional a) => (Double, Double) -> (Double -> a) -> g -> (a, g)
308 randomIvalDouble (l,h) fromDouble rng
309 | l > h = randomIvalDouble (h,l) fromDouble rng
311 case (randomIvalInteger (toInteger (minBound::Int), toInteger (maxBound::Int)) rng) of
315 fromDouble ((l+h)/2) +
316 fromDouble ((h-l) / realToFrac intRange) *
317 fromIntegral (x::Int)
322 intRange = toInteger (maxBound::Int) - toInteger (minBound::Int)
324 iLogBase :: Integer -> Integer -> Integer
325 iLogBase b i = if i < b then 1 else 1 + iLogBase b (i `div` b)
327 stdNext :: StdGen -> (Int, StdGen)
328 stdNext (StdGen s1 s2) = (z', StdGen s1'' s2'')
329 where z' = if z < 1 then z + 2147483562 else z
333 s1' = 40014 * (s1 - k * 53668) - k * 12211
334 s1'' = if s1' < 0 then s1' + 2147483563 else s1'
337 s2' = 40692 * (s2 - k' * 52774) - k' * 3791
338 s2'' = if s2' < 0 then s2' + 2147483399 else s2'
340 stdSplit :: StdGen -> (StdGen, StdGen)
341 stdSplit std@(StdGen s1 s2)
344 -- no statistical foundation for this!
345 left = StdGen new_s1 t2
346 right = StdGen t1 new_s2
348 new_s1 | s1 == 2147483562 = 1
351 new_s2 | s2 == 1 = 2147483398
354 StdGen t1 t2 = snd (next std)
356 -- The global random number generator
360 There is a single, implicit, global random number generator of type
361 'StdGen', held in some global variable maintained by the 'IO' monad. It is
362 initialised automatically in some system-dependent fashion, for example, by
363 using the time of day, or Linux's kernel random number generator. To get
364 deterministic behaviour, use 'setStdGen'.
367 -- |'setStdGen' sets the global random number generator.
368 setStdGen :: StdGen -> IO ()
369 setStdGen sgen = writeIORef theStdGen sgen
371 -- |'getStdGen' gets the global random number generator.
372 getStdGen :: IO StdGen
373 getStdGen = readIORef theStdGen
375 -- |'newStdGen' applies 'split' to the current global random generator, updates it
376 -- with one of the results, and returns the other.
377 theStdGen :: IORef StdGen
378 theStdGen = unsafePerformIO $ do
382 newStdGen :: IO StdGen
385 let (a,b) = split rng
389 {- |'getStdRandom' uses the supplied function to get a value from the current
390 global random generator, and updates the global generator with the new generator
391 returned by the function. For example, 'rollDice' gets a random integer between 1 and 6:
394 > rollDice = getStdRandom (randomR (1,6))
398 getStdRandom :: (StdGen -> (a,StdGen)) -> IO a
401 let (v, new_rng) = f rng
407 * [1] FW Burton and RL Page, /Distributed random number generation/,
408 Journal of Functional Programming, 2(2):203-212, April 1992.
410 * [2] SK #Park# Park, and KW Miller, /Random number generators -
411 good ones are hard to find/, Comm ACM 31(10), Oct 1988, pp1192-1201.
413 * [3] DG #Carta# Carta, /Two fast implementations of the minimal standard
414 random number generator/, Comm ACM, 33(1), Jan 1990, pp87-88.
416 * [4] P Hellekalek, /Don\'t trust parallel Monte Carlo/,
417 Department of Mathematics, University of Salzburg,
418 <http://random.mat.sbg.ac.at/~peter/pads98.ps>, 1998.
420 The Web site <http://random.mat.sbg.ac.at/> is a great source of information.