Copyright | (c) 2009-2012 Bryan O'Sullivan |
---|---|
License | BSD3 |
Maintainer | bos@serpentine.com |
Stability | experimental |
Portability | portable |
Safe Haskell | None |
Language | Haskell2010 |
Pseudo-random number generation using Marsaglia's MWC256, (also
known as MWC8222) multiply-with-carry generator, which has a period
of \(2^{8222}\) and fares well in tests of randomness. It is also
extremely fast, between 2 and 3 times faster than the Mersenne
Twister. There're two representation of generator: Gen
which is
generator that uses in-place mutation and Seed
which is immutable
snapshot of generator's state.
Initialization
Generator could be initialized in several ways. One is to obtain
randomness from operating system using createSystemRandom
,
createSystemSeed
or withSystemRandomST
(All examples assume
that System.Random.Stateful
is imported)
>>>
g <- createSystemRandom
>>>
uniformM g :: IO Int
...
>>>
withSystemRandomST $ \g -> uniformM g :: IO Int
...
Deterministically create generator from given seed using
initialize
function:
>>>
import Data.Int
>>>
import qualified Data.Vector.Unboxed as U
>>>
import System.Random.Stateful
>>>
g <- initialize $ U.fromList [1,2,3]
>>>
uniformRM (1,200) g :: IO Int64
101
Last way is to create generator with fixed seed which could be useful in testing
>>>
g <- create
>>>
uniformM g :: IO Int
-8765701622605876598
Generation of random numbers
Recommended way of generating random numbers in simple cases like
generating uniformly distributed random number in range or value
uniformly distributed in complete type domain is to use
UniformRange
and Uniform
type classes. Note that while small
self-contained examples usually require explicit annotations
usually result type could be inferred.
This example simulates 20 throws of fair 6-sided dice:
>>>
g <- create
>>>
replicateM 20 $ uniformRM (1, 6::Integer) g
[3,4,3,1,4,6,1,6,1,4,2,2,3,2,4,2,5,1,3,5]
For generating full range of possible values one could use
uniformM
. This example generates 10 random bytes, or equivalently
10 throws of 256-sided dice:
>>>
g <- create
>>>
replicateM 10 $ uniformM g :: IO [Word8]
[209,138,126,150,165,15,69,203,155,146]
There're special functions for generation of Doubles
and @Float
in unit interval: uniformDouble01M
,
uniformDoublePositive01M
, uniformFloat01M
,
uniformFloatPositive01M
:
>>>
uniformDouble01M =<< create
0.5248103628705498>>>
uniformFloat01M =<< create
0.5248104
For normal distribution and others see modules
System.Random.MWC.Distributions and
System.Random.MWC.CondensedTable. Note that they could be used
with any other generator implementing StatefulGen
API
There're special cases for generating random vectors and bytestrings. For example in order to generate random 10-byte sequences as unboxed vector or bytestring:
>>>
g <- create
>>>
uniformVector g 10 :: IO (U.Vector Word8)
[209,138,126,150,165,15,69,203,155,146]
>>>
import qualified Data.ByteString as BS
>>>
g <- create
>>>
BS.unpack <$> uniformByteStringM 10 g
[138,242,130,33,209,248,89,134,150,180]
Note that uniformByteStringM
produces different result
from uniformVector
since it uses PRNG's output more efficently.
State handling
For repeatability, the state of the generator can be snapshotted
and replayed using the save
and restore
functions. Following
example shows how to save and restore generator:
>>>
g <- create
>>>
replicateM_ 10 (uniformM g :: IO Word64)
>>>
s <- save g
>>>
uniformM g :: IO Word32
1771812561>>>
uniformM =<< restore s :: IO Word32
1771812561
Synopsis
- data Gen s
- create :: PrimMonad m => m (Gen (PrimState m))
- initialize :: (PrimMonad m, Vector v Word32) => v Word32 -> m (Gen (PrimState m))
- createSystemSeed :: IO Seed
- createSystemRandom :: IO GenIO
- withSystemRandomST :: (forall s. Gen s -> ST s a) -> IO a
- type GenIO = Gen (PrimState IO)
- type GenST s = Gen (PrimState (ST s))
- asGenIO :: (GenIO -> IO a) -> GenIO -> IO a
- asGenST :: (GenST s -> ST s a) -> GenST s -> ST s a
- class Uniform a where
- uniformM :: StatefulGen g m => g -> m a
- class UniformRange a where
- uniformRM :: StatefulGen g m => (a, a) -> g -> m a
- class Variate a where
- uniformVector :: (PrimMonad m, StatefulGen g m, Uniform a, Vector v a) => g -> Int -> m (v a)
- data Seed
- fromSeed :: Seed -> Vector Word32
- toSeed :: Vector v Word32 => v Word32 -> Seed
- save :: PrimMonad m => Gen (PrimState m) -> m Seed
- restore :: PrimMonad m => Seed -> m (Gen (PrimState m))
- withSystemRandom :: PrimBase m => (Gen (PrimState m) -> m a) -> IO a
Gen: Pseudo-Random Number Generators
State of the pseudo-random number generator. It uses mutable state so same generator shouldn't be used from the different threads simultaneously.
Instances
(s ~ PrimState m, PrimMonad m) => StatefulGen (Gen s) m Source # | Since: 0.15.0.0 |
Defined in System.Random.MWC uniformWord32R :: Word32 -> Gen s -> m Word32 # uniformWord64R :: Word64 -> Gen s -> m Word64 # uniformWord8 :: Gen s -> m Word8 # uniformWord16 :: Gen s -> m Word16 # uniformWord32 :: Gen s -> m Word32 # uniformWord64 :: Gen s -> m Word64 # uniformShortByteString :: Int -> Gen s -> m ShortByteString # |
create :: PrimMonad m => m (Gen (PrimState m)) Source #
Create a generator for variates using a fixed seed.
initialize :: (PrimMonad m, Vector v Word32) => v Word32 -> m (Gen (PrimState m)) Source #
Create a generator for variates using the given seed, of which up to 256 elements will be used. For arrays of less than 256 elements, part of the default seed will be used to finish initializing the generator's state.
Examples:
initialize (singleton 42)
initialize (fromList [4, 8, 15, 16, 23, 42])
If a seed contains fewer than 256 elements, it is first used
verbatim, then its elements are xor
ed against elements of the
default seed until 256 elements are reached.
If a seed contains exactly 258 elements, then the last two elements
are used to set the generator's initial state. This allows for
complete generator reproducibility, so that e.g. gen' == gen
in
the following example:
gen' <-initialize
.fromSeed
=<<save
In the MWC algorithm, the carry value must be strictly smaller than the multiplicator (see https://en.wikipedia.org/wiki/Multiply-with-carry). Hence, if a seed contains exactly 258 elements, the carry value, which is the last of the 258 values, is moduloed by the multiplicator.
Note that if the first carry value is strictly smaller than the multiplicator,
all subsequent carry values are also strictly smaller than the multiplicator
(a proof of this is in the comments of the code of uniformWord32
), hence
when restoring a saved state, we have the guarantee that moduloing the saved
carry won't modify its value.
createSystemSeed :: IO Seed Source #
Generate random seed for generator using system's fast source of pseudo-random numbers.
Since: 0.15.0.0
createSystemRandom :: IO GenIO Source #
Seed a PRNG with data from the system's fast source of pseudo-random numbers.
withSystemRandomST :: (forall s. Gen s -> ST s a) -> IO a Source #
Seed PRNG with data from the system's fast source of pseudo-random numbers and execute computation in ST monad.
Since: 0.15.0.0
Type helpers
The functions in this package are deliberately written for
flexibility, and will run in both the IO
and ST
monads.
This can defeat the compiler's ability to infer a principal type in simple (and common) cases. For instance, we would like the following to work cleanly:
import System.Random.MWC import Data.Vector.Unboxed main = do v <- withSystemRandom $ \gen -> uniformVector gen 20 print (v :: Vector Int)
Unfortunately, the compiler cannot tell what monad uniformVector
should execute in. The "fix" of adding explicit type annotations
is not pretty:
{-# LANGUAGE ScopedTypeVariables #-} import Control.Monad.ST main = do vs <- withSystemRandom $ \(gen::GenST s) -> uniformVector gen 20 :: ST s (Vector Int) print vs
As a more readable alternative, this library provides asGenST
and
asGenIO
to constrain the types appropriately. We can get rid of
the explicit type annotations as follows:
main = do vs <- withSystemRandom . asGenST $ \gen -> uniformVector gen 20 print (vs :: Vector Int)
This is almost as compact as the original code that the compiler rejected.
asGenIO :: (GenIO -> IO a) -> GenIO -> IO a Source #
Constrain the type of an action to run in the IO
monad.
asGenST :: (GenST s -> ST s a) -> GenST s -> ST s a Source #
Constrain the type of an action to run in the ST
monad.
Variates: uniformly distributed values
The class of types for which a uniformly distributed value can be drawn from all possible values of the type.
Since: random-1.2.0
uniformM :: StatefulGen g m => g -> m a #
Generates a value uniformly distributed over all possible values of that type.
Since: random-1.2.0
Instances
class UniformRange a where #
The class of types for which a uniformly distributed value can be drawn from a range.
Since: random-1.2.0
uniformRM :: StatefulGen g m => (a, a) -> g -> m a #
Generates a value uniformly distributed over the provided range, which is interpreted as inclusive in the lower and upper bound.
uniformRM (1 :: Int, 4 :: Int)
generates values uniformly from the set \(\{1,2,3,4\}\)uniformRM (1 :: Float, 4 :: Float)
generates values uniformly from the set \(\{x\;|\;1 \le x \le 4\}\)
The following law should hold to make the function always defined:
uniformRM (a, b) = uniformRM (b, a)
Since: random-1.2.0
Instances
class Variate a where Source #
NOTE: Consider use of more principled type classes
Uniform
and UniformRange
instead.
The class of types for which we can generate uniformly distributed random variates.
The uniform PRNG uses Marsaglia's MWC256 (also known as MWC8222) multiply-with-carry generator, which has a period of 2^8222 and fares well in tests of randomness. It is also extremely fast, between 2 and 3 times faster than the Mersenne Twister.
Note: Marsaglia's PRNG is not known to be cryptographically secure, so you should not use it for cryptographic operations.
uniform :: PrimMonad m => Gen (PrimState m) -> m a Source #
Generate a single uniformly distributed random variate. The range of values produced varies by type:
- For fixed-width integral types, the type's entire range is used.
- For floating point numbers, the range (0,1] is used. Zero is
explicitly excluded, to allow variates to be used in
statistical calculations that require non-zero values
(e.g. uses of the
log
function).
To generate a Float
variate with a range of [0,1), subtract
2**(-33). To do the same with Double
variates, subtract
2**(-53).
uniformR :: PrimMonad m => (a, a) -> Gen (PrimState m) -> m a Source #
Generate single uniformly distributed random variable in a given range.
- For integral types inclusive range is used.
- For floating point numbers range (a,b] is used if one ignores rounding errors.
Instances
Variate Bool Source # | |
Variate Double Source # | |
Variate Float Source # | |
Variate Int Source # | |
Variate Int8 Source # | |
Variate Int16 Source # | |
Variate Int32 Source # | |
Variate Int64 Source # | |
Variate Word Source # | |
Variate Word8 Source # | |
Variate Word16 Source # | |
Variate Word32 Source # | |
Variate Word64 Source # | |
(Variate a, Variate b) => Variate (a, b) Source # | |
(Variate a, Variate b, Variate c) => Variate (a, b, c) Source # | |
(Variate a, Variate b, Variate c, Variate d) => Variate (a, b, c, d) Source # | |
uniformVector :: (PrimMonad m, StatefulGen g m, Uniform a, Vector v a) => g -> Int -> m (v a) Source #
Generate a vector of pseudo-random variates. This is not
necessarily faster than invoking uniform
repeatedly in a loop,
but it may be more convenient to use in some situations.
Seed: state management
An immutable snapshot of the state of a Gen
.
Instances
Eq Seed Source # | |
Show Seed Source # | |
PrimMonad m => FrozenGen Seed m Source # | Since: 0.15.0.0 |
Defined in System.Random.MWC type MutableGen Seed m = (g :: Type) # freezeGen :: MutableGen Seed m -> m Seed # thawGen :: Seed -> m (MutableGen Seed m) # | |
type MutableGen Seed m Source # | |
Defined in System.Random.MWC |
toSeed :: Vector v Word32 => v Word32 -> Seed Source #
Convert vector to Seed
. It acts similarily to initialize
and
will accept any vector. If you want to pass seed immediately to
restore you better call initialize directly since following law holds:
restore (toSeed v) = initialize v
Deprecated
withSystemRandom :: PrimBase m => (Gen (PrimState m) -> m a) -> IO a Source #
Deprecated: Use withSystemRandomST or createSystemSeed or createSystemRandom instead
Seed a PRNG with data from the system's fast source of pseudo-random numbers, then run the given action.
This function is unsafe and for example allows STRefs or any other mutable data structure to escape scope:
>>>
ref <- withSystemRandom $ \_ -> newSTRef 1
>>>
withSystemRandom $ \_ -> modifySTRef ref succ >> readSTRef ref
2>>>
withSystemRandom $ \_ -> modifySTRef ref succ >> readSTRef ref
3
References
- Marsaglia, G. (2003) Seeds for random number generators. Communications of the ACM 46(5):90–93. http://doi.acm.org/10.1145/769800.769827
- Doornik, J.A. (2007) Conversion of high-period random numbers to floating point. ACM Transactions on Modeling and Computer Simulation 17(1). http://www.doornik.com/research/randomdouble.pdf