Copyright | (c) 2009-2012 Bryan O'Sullivan |
---|---|

License | BSD3 |

Maintainer | bos@serpentine.com |

Stability | experimental |

Portability | portable |

Safe Haskell | None |

Language | Haskell98 |

Pseudo-random number generation. This module contains code for generating high quality random numbers that follow a uniform distribution.

For non-uniform distributions, see the
`Distributions`

module.

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.

The generator state is stored in the `Gen`

data type. It can be
created in several ways:

- Using the
`withSystemRandom`

call, which creates a random state. - Supply your own seed to
`initialize`

function. - Finally,
`create`

makes a generator from a fixed seed. Generators created in this way aren't really random.

For repeatability, the state of the generator can be snapshotted
and replayed using the `save`

and `restore`

functions.

The simplest use is to generate a vector of uniformly distributed values:

vs <-`withSystemRandom`

.`asGenST`

$ \gen ->`uniformVector`

gen 100

These values can be of any type which is an instance of the class
`Variate`

.

To generate random values on demand, first `create`

a random number
generator.

` gen <- ``create`

Hold onto this generator and use it wherever random values are
required (creating a new generator is expensive compared to
generating a random number, so you don't want to throw them
away). Get a random value using `uniform`

or `uniformR`

:

` v <- ``uniform`

gen

` v <- ``uniformR`

(1, 52) gen

## Synopsis

- data Gen s
- create :: PrimMonad m => m (Gen (PrimState m))
- initialize :: (PrimMonad m, Vector v Word32) => v Word32 -> m (Gen (PrimState m))
- withSystemRandom :: PrimBase m => (Gen (PrimState m) -> m a) -> IO a
- createSystemRandom :: IO GenIO
- 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 Variate a where
- uniformVector :: (PrimMonad m, Variate a, Vector v a) => Gen (PrimState m) -> 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))

# 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.

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.

withSystemRandom :: PrimBase m => (Gen (PrimState m) -> m a) -> IO a Source #

Seed a PRNG with data from the system's fast source of
pseudo-random numbers ("`/dev/urandom`

" on Unix-like systems or
`RtlGenRandom`

on Windows), then run the given action.

This is a somewhat expensive function, and is intended to be called
only occasionally (e.g. once per thread). You should use the `Gen`

it creates to generate many random numbers.

createSystemRandom :: IO GenIO Source #

Seed a PRNG with data from the system's fast source of pseudo-random
numbers. All the caveats of `withSystemRandom`

apply here as well.

## 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

class Variate a where Source #

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, Variate a, Vector v a) => Gen (PrimState m) -> 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`

.

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

# 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