-- Stability : stable
-- Portability : portable
--
--- Random numbers.
+-- This library deals with the common task of pseudo-random number
+-- generation. The library makes it possible to generate repeatable
+-- results, by starting with a specified initial random number generator,
+-- or to get different results on each run by using the system-initialised
+-- generator or by supplying a seed from some other source.
+--
+-- The library is split into two layers:
+--
+-- * A core /random number generator/ provides a supply of bits.
+-- The class 'RandomGen' provides a common interface to such generators.
+-- The library provides one instance of 'RandomGen', the abstract
+-- data type 'StdGen'. Programmers may, of course, supply their own
+-- instances of 'RandomGen'.
+--
+-- * The class 'Random' provides a way to extract values of a particular
+-- type from a random number generator. For example, the 'Float'
+-- instance of 'Random' allows one to generate random values of type
+-- 'Float'.
+--
+-- This implementation uses the Portable Combined Generator of L'Ecuyer
+-- ["System.Random\#LEcuyer"] for 32-bit computers, transliterated by
+-- Lennart Augustsson. It has a period of roughly 2.30584e18.
--
-----------------------------------------------------------------------------
-- $intro
- -- * The 'RandomGen' class, and the 'StdGen' generator
+ -- * Random number generators
RandomGen(next, split, genRange)
+
+ -- ** Standard random number generators
, StdGen
, mkStdGen
- -- * The 'Random' class
- , Random ( random, randomR,
- randoms, randomRs,
- randomIO, randomRIO )
-
- -- * The global random number generator
+ -- ** The global random number generator
-- $globalrng
, setStdGen
, newStdGen
+ -- * Random values of various types
+ , Random ( random, randomR,
+ randoms, randomRs,
+ randomIO, randomRIO )
+
-- * References
-- $references
getClockTime = do t <- readtime nullPtr; return (TOD (toInteger t) ())
#endif
-{- $intro
-
-This library deals with the common task of pseudo-random
-number generation. The library makes it possible to generate
-repeatable results, by starting with a specified initial random
-number generator; or to get different results on each run by using the
-system-initialised generator, or by supplying a seed from some other
-source.
-
-The library is split into two layers:
-
-* A core /random number generator/ provides a supply of bits. The class
-'RandomGen' provides a common interface to such generators.
-
-* The class 'Random' provides a way to extract particular values from
-a random number generator. For example, the 'Float' instance of 'Random'
-allows one to generate random values of type 'Float'.
-
-[Comment found in this file when merging with Library Report:]
-
-The June 1988 (v31 \#6) issue of the Communications of the ACM has an
-article by Pierre L'Ecuyer called, /Efficient and Portable Combined
-Random Number Generators/. Here is the Portable Combined Generator of
-L'Ecuyer for 32-bit computers. It has a period of roughly 2.30584e18.
-
-Transliterator: Lennart Augustsson
-
--}
-
-- | The class 'RandomGen' provides a common interface to random number
-- generators.
+--
+-- Minimal complete definition: 'next' and 'split'.
class RandomGen g where
- -- |The 'next' operation allows one to extract at least 30 bits (one 'Int''s
- -- worth) from the generator, returning a new generator as well. The
- -- integer returned may be positive or negative.
+ -- |The 'next' operation returns an 'Int' that is uniformly distributed
+ -- in the range returned by 'genRange' (including both end points),
+ -- and a new generator.
next :: g -> (Int, g)
-- |The 'split' operation allows one to obtain two distinct random number
-- generators. This is very useful in functional programs (for example, when
-- passing a random number generator down to recursive calls), but very
-- little work has been done on statistically robust implementations of
- -- 'split' ([1,4] are the only examples we know of).
+ -- 'split' (["System.Random\#Burton", "System.Random\#Hellekalek"]
+ -- are the only examples we know of).
split :: g -> (g, g)
-- |The 'genRange' operation yields the range of values returned by
--
-- * If @(a,b) = 'genRange' g@, then @a < b@.
--
- -- * 'genRange' is not strict.
+ -- * 'genRange' always returns a pair of defined 'Int's.
--
-- The second condition ensures that 'genRange' cannot examine its
-- argument, and hence the value it returns can be determined only by the
-- a single call to 'genRange' to establish a generator's range, without
-- being concerned that the generator returned by (say) 'next' might have
-- a different range to the generator passed to 'next'.
+ --
+ -- The default definition spans the full range of 'Int'.
genRange :: g -> (Int,Int)
-- default method
genRange g = (minBound,maxBound)
-{- |The "System.Random" library provides one instance of 'RandomGen', the
-abstract data type 'StdGen'.
-
+{- |
The 'StdGen' instance of 'RandomGen' has a 'genRange' of at least 30 bits.
The result of repeatedly using 'next' should be at least as statistically
that 'split' deliver generators that are (a) not identical and
(b) independently robust in the sense just given.
-The 'Show'\/'Read' instances of 'StdGen' provide a primitive way to save the
+The 'Show' and 'Read' instances of 'StdGen' provide a primitive way to save the
state of a random number generator.
It is required that @'read' ('show' g) == g@.
instance RandomGen StdGen where
next = stdNext
split = stdSplit
+ genRange _ = stdRange
instance Show StdGen where
showsPrec p (StdGen s1 s2) =
The function 'mkStdGen' provides an alternative way of producing an initial
generator, by mapping an 'Int' into a generator. Again, distinct arguments
should be likely to produce distinct generators.
-
-Programmers may, of course, supply their own instances of 'RandomGen'.
-}
mkStdGen :: Int -> StdGen -- why not Integer ?
mkStdGen s
iLogBase :: Integer -> Integer -> Integer
iLogBase b i = if i < b then 1 else 1 + iLogBase b (i `div` b)
+stdRange :: (Int,Int)
+stdRange = (0, 2147483562)
+
stdNext :: StdGen -> (Int, StdGen)
+-- Returns values in the range stdRange
stdNext (StdGen s1 s2) = (z', StdGen s1'' s2'')
where z' = if z < 1 then z + 2147483562 else z
z = s1'' - s2''
{- $references
-1. FW Burton and RL Page, /Distributed random number generation/,
+1. FW #Burton# Burton and RL Page, /Distributed random number generation/,
Journal of Functional Programming, 2(2):203-212, April 1992.
2. SK #Park# Park, and KW Miller, /Random number generators -
3. DG #Carta# Carta, /Two fast implementations of the minimal standard
random number generator/, Comm ACM, 33(1), Jan 1990, pp87-88.
-4. P Hellekalek, /Don\'t trust parallel Monte Carlo/,
+4. P #Hellekalek# Hellekalek, /Don\'t trust parallel Monte Carlo/,
Department of Mathematics, University of Salzburg,
<http://random.mat.sbg.ac.at/~peter/pads98.ps>, 1998.
+5. Pierre #LEcuyer# L'Ecuyer, /Efficient and portable combined random
+number generators/, Comm ACM, 31(6), Jun 1988, pp742-749.
+
The Web site <http://random.mat.sbg.ac.at/> is a great source of information.
-}