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 )
52 #ifdef __GLASGOW_HASKELL__
53 import GHC.Show ( showSignedInt, showSpace )
54 import Numeric ( readDec )
55 import GHC.IOBase ( unsafePerformIO, stToIO )
56 import System.Time ( getClockTime, ClockTime(..) )
61 The "Random" library deals with the common task of pseudo-random
62 number generation. The library makes it possible to generate
63 repeatable results, by starting with a specified initial random
64 number generator; or to get different results on each run by using the
65 system-initialised generator, or by supplying a seed from some other
68 The library is split into two layers:
70 * A core /random number generator/ provides a supply of bits. The class
71 'RandomGen' provides a common interface to such generators.
73 * The class 'Random' provides a way to extract particular values from
74 a random number generator. For example, the 'Float' instance of 'Random'
75 allows one to generate random values of type 'Float'.
77 [Comment found in this file when merging with Library Report:]
79 The June 1988 (v31 \#6) issue of the Communications of the ACM has an
80 article by Pierre L'Ecuyer called, /Efficient and Portable Combined
81 Random Number Generators/. Here is the Portable Combined Generator of
82 L'Ecuyer for 32-bit computers. It has a period of roughly 2.30584e18.
84 Transliterator: Lennart Augustsson
89 -- The class 'RandomGen' provides a common interface to random number generators.
91 class RandomGen g where
93 -- |The 'next' operation allows one to extract at least 30 bits (one 'Int''s
94 -- worth) from the generator, returning a new generator as well. The
95 -- integer returned may be positive or negative.
98 -- |The 'split' operation allows one to obtain two distinct random number
99 -- generators. This is very useful in functional programs (for example, when
100 -- passing a random number generator down to recursive calls), but very
101 -- little work has been done on statistically robust implementations of
102 -- @split ([1,4]@ are the only examples we know of).
105 genRange :: g -> (Int,Int)
108 genRange g = (minBound,maxBound)
110 {- |The "Random" library provides one instance of 'RandomGen', the abstract data
113 The result of repeatedly using next should be at least as statistically robust
114 as the /Minimal Standard Random Number Generator/ described by
115 ["System.Random\#Park", "System.Random\#Carta"]. Until more
116 is known about implementations of 'split', all we require is that 'split' deliver
117 generators that are (a) not identical and (b) independently robust in the sense
120 The 'show'\/'Read' instances of 'StdGen' provide a primitive way to save the
121 state of a random number generator. It is required that @read (show g) == g@.
123 In addition, 'read' may be used to map an arbitrary string (not necessarily one
124 produced by 'show') onto a value of type 'StdGen'. In general, the 'read'
125 instance of 'StdGen' has the following properties:
127 * It guarantees to succeed on any string.
129 *It guarantees to consume only a finite portion of the string.
131 * Different argument strings are likely to result in different results.
133 The function 'mkStdGen' provides an alternative way of producing an initial
134 generator, by mapping an 'Int' into a generator. Again, distinct arguments
135 should be likely to produce distinct generators.
137 Programmers may, of course, supply their own instances of 'RandomGen'.
144 instance RandomGen StdGen where
148 #ifdef __GLASGOW_HASKELL__
149 instance Show StdGen where
150 showsPrec p (StdGen s1 s2) =
157 instance Show StdGen where
158 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 : randoms g' where (x,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 #ifdef __GLASGOW_HASKELL__
286 mkStdRNG :: Integer -> IO StdGen
289 (TOD sec _) <- getClockTime
290 return (createStdGen (sec * 12345 + ct + o))
294 mkStdRNG :: Integer -> IO StdGen
297 return (createStdGen (ct + o))
300 randomIvalInteger :: (RandomGen g, Num a) => (Integer, Integer) -> g -> (a, g)
301 randomIvalInteger (l,h) rng
302 | l > h = randomIvalInteger (h,l) rng
303 | otherwise = case (f n 1 rng) of (v, rng') -> (fromInteger (l + v `mod` k), rng')
314 f (n-1) (fromIntegral x + acc * b) g'
316 randomIvalDouble :: (RandomGen g, Fractional a) => (Double, Double) -> (Double -> a) -> g -> (a, g)
317 randomIvalDouble (l,h) fromDouble rng
318 | l > h = randomIvalDouble (h,l) fromDouble rng
320 case (randomIvalInteger (toInteger (minBound::Int), toInteger (maxBound::Int)) rng) of
324 fromDouble ((l+h)/2) +
325 fromDouble ((h-l) / realToFrac intRange) *
326 fromIntegral (x::Int)
331 intRange = toInteger (maxBound::Int) - toInteger (minBound::Int)
333 iLogBase :: Integer -> Integer -> Integer
334 iLogBase b i = if i < b then 1 else 1 + iLogBase b (i `div` b)
336 stdNext :: StdGen -> (Int, StdGen)
337 stdNext (StdGen s1 s2) = (z', StdGen s1'' s2'')
338 where z' = if z < 1 then z + 2147483562 else z
342 s1' = 40014 * (s1 - k * 53668) - k * 12211
343 s1'' = if s1' < 0 then s1' + 2147483563 else s1'
346 s2' = 40692 * (s2 - k' * 52774) - k' * 3791
347 s2'' = if s2' < 0 then s2' + 2147483399 else s2'
349 stdSplit :: StdGen -> (StdGen, StdGen)
350 stdSplit std@(StdGen s1 s2)
353 -- no statistical foundation for this!
354 left = StdGen new_s1 t2
355 right = StdGen t1 new_s2
357 new_s1 | s1 == 2147483562 = 1
360 new_s2 | s2 == 1 = 2147483398
363 StdGen t1 t2 = snd (next std)
365 -- The global random number generator
369 There is a single, implicit, global random number generator of type
370 'StdGen', held in some global variable maintained by the 'IO' monad. It is
371 initialised automatically in some system-dependent fashion, for example, by
372 using the time of day, or Linux's kernel random number generator. To get
373 deterministic behaviour, use 'setStdGen'.
376 -- |'setStdGen' sets the global random number generator.
377 setStdGen :: StdGen -> IO ()
378 setStdGen sgen = writeIORef theStdGen sgen
380 -- |'getStdGen' gets the global random number generator.
381 getStdGen :: IO StdGen
382 getStdGen = readIORef theStdGen
384 -- |'newStdGen' applies 'split' to the current global random generator, updates it
385 -- with one of the results, and returns the other.
386 theStdGen :: IORef StdGen
387 theStdGen = unsafePerformIO $ do
391 newStdGen :: IO StdGen
394 let (a,b) = split rng
398 {- |'getStdRandom' uses the supplied function to get a value from the current
399 global random generator, and updates the global generator with the new generator
400 returned by the function. For example, 'rollDice' gets a random integer between 1 and 6:
403 > rollDice = getStdRandom (randomR (1,6))
407 getStdRandom :: (StdGen -> (a,StdGen)) -> IO a
410 let (v, new_rng) = f rng
416 * [1] FW Burton and RL Page, /Distributed random number generation/,
417 Journal of Functional Programming, 2(2):203-212, April 1992.
419 * [2] SK #Park# Park, and KW Miller, /Random number generators -
420 good ones are hard to find/, Comm ACM 31(10), Oct 1988, pp1192-1201.
422 * [3] DG #Carta# Carta, /Two fast implementations of the minimal standard
423 random number generator/, Comm ACM, 33(1), Jan 1990, pp87-88.
425 * [4] P Hellekalek, /Don\'t trust parallel Monte Carlo/,
426 Department of Mathematics, University of Salzburg,
427 <http://random.mat.sbg.ac.at/~peter/pads98.ps>, 1998.
429 The Web site <http://random.mat.sbg.ac.at/> is a great source of information.