std.random

Facilities for random number generation.

The new-style generator objects hold their own state so they are immune of threading issues. The generators feature a number of well-known and well-documented methods of generating random numbers. An overall fast and reliable means to generate random numbers is the Mt19937 generator, which derives its name from "Mersenne Twister with a period of 2 to the power of 19937". In memory-constrained situations, linear congruential generators such as MinstdRand0 and MinstdRand might be useful. The standard library provides an alias Random for whichever generator it considers the most fit for the target environment.

Example:

// Generate a uniformly-distributed integer in the range [0, 14]
auto i = uniform(0, 15);
// Generate a uniformly-distributed real in the range [0, 100$(RPAREN)
// using a specific random generator
Random gen;
auto r = uniform(0.0L, 100.0L, gen);

In addition to random number generators, this module features distributions, which skew a generator's output statistical distribution in various ways. So far the uniform distribution for integers and real numbers have been implemented.

Source:
std/random.d

License:
Boost License 1.0.

Authors:
Andrei Alexandrescu Masahiro Nakagawa (Xorshift randome generator) Joseph Rushton Wakeling (Algorithm D for random sampling)

Credits:
The entire random number library architecture is derived from the excellent C++0X random number facility proposed by Jens Maurer and contributed to by researchers at the Fermi laboratory(excluding Xorshift).

template isUniformRNG(Rng, ElementType)
template isUniformRNG(Rng)

Test if Rng is a random-number generator. The overload taking a ElementType also makes sure that the Rng generates values of that type.

A random-number generator has at least the following features:

• it's an InputRange
• it has a 'bool isUniformRandom' field readable in CTFE

template isSeedable(Rng, SeedType)
template isSeedable(Rng)

Test if Rng is seedable. The overload taking a SeedType also makes sure that the Rng can be seeded with SeedType.

A seedable random-number generator has the following additional features:

• it has a 'seed(ElementType)' function

struct LinearCongruentialEngine(UIntType, UIntType a, UIntType c, UIntType m) if (isUnsigned!UIntType);

Linear Congruential generator.

bool isUniformRandom;

Mark this as a Rng

bool hasFixedRange;

Does this generator have a fixed range? (true).

UIntType min;

Lowest generated value (1 if c == 0, 0 otherwise).

UIntType max;

Highest generated value (modulus - 1).

UIntType multiplier;
UIntType increment;
UIntType modulus;

The parameters of this distribution. The random number is x = (x * multipler + increment) % modulus.

pure @safe this(UIntType x0);

Constructs a LinearCongruentialEngine generator seeded with x0.

pure @safe void seed(UIntType x0 = 1);

(Re)seeds the generator.

pure nothrow @safe void popFront();

Advances the random sequence.

const pure nothrow @property @safe UIntType front();

Returns the current number in the random sequence.

pure nothrow @property @safe typeof(this) save();

bool empty;

Always false (random generators are infinite ranges).

const pure nothrow @safe bool opEquals(ref const LinearCongruentialEngine rhs);

Compares against rhs for equality.

alias MinstdRand0 = LinearCongruentialEngine!(uint, 16807u, 0u, 2147483647u).LinearCongruentialEngine;
alias MinstdRand = LinearCongruentialEngine!(uint, 48271u, 0u, 2147483647u).LinearCongruentialEngine;

Define LinearCongruentialEngine generators with well-chosen parameters. MinstdRand0 implements Park and Miller's "minimal standard" generator that uses 16807 for the multiplier. MinstdRand implements a variant that has slightly better spectral behavior by using the multiplier 48271. Both generators are rather simplistic.

Example:

// seed with a constant
auto rnd0 = MinstdRand0(1);
auto n = rnd0.front; // same for each run
// Seed with an unpredictable value
rnd0.seed(unpredictableSeed);
n = rnd0.front; // different across runs

struct MersenneTwisterEngine(UIntType, size_t w, size_t n, size_t m, size_t r, UIntType a, size_t u, size_t s, UIntType b, size_t t, UIntType c, size_t l) if (isUnsigned!UIntType);

The Mersenne Twister generator.

bool isUniformRandom;

Mark this as a Rng

size_t wordSize;
size_t stateSize;
size_t shiftSize;
size_t maskBits;
UIntType xorMask;
UIntType temperingU;
size_t temperingS;
UIntType temperingB;
size_t temperingT;
UIntType temperingC;
size_t temperingL;

Parameters for the generator.

UIntType min;

Smallest generated value (0).

UIntType max;

Largest generated value.

UIntType defaultSeed;

The default seed value.

pure nothrow @safe this(UIntType value);

Constructs a MersenneTwisterEngine object.

pure nothrow @safe void seed()(UIntType value = defaultSeed);

Seeds a MersenneTwisterEngine object.

Note:
This seed function gives 2^32 starting points. To allow the RNG to be started in any one of its internal states use the seed overload taking an InputRange.

void seed(T)(T range) if (isInputRange!T && is(Unqual!(ElementType!T) == UIntType));

Seeds a MersenneTwisterEngine object using an InputRange.

Throws:
Exception if the InputRange didn't provide enough elements to seed the generator. The number of elements required is the 'n' template parameter of the MersenneTwisterEngine struct.

Examples:

Mt19937 gen;
gen.seed(map!((a) => unpredictableSeed)(repeat(0)));

pure nothrow @safe void popFront();

Advances the generator.

pure nothrow @property @safe UIntType front();

Returns the current random value.

pure nothrow @property @safe typeof(this) save();

bool empty;

Always false.

alias Mt19937 = MersenneTwisterEngine!(uint, 32LU, 624LU, 397LU, 31LU, 2567483615u, 11LU, 7LU, 2636928640u, 15LU, 4022730752u, 18LU).MersenneTwisterEngine;

A MersenneTwisterEngine instantiated with the parameters of the original engine MT19937, generating uniformly-distributed 32-bit numbers with a period of 2 to the power of 19937. Recommended for random number generation unless memory is severely restricted, in which case a LinearCongruentialEngine would be the generator of choice.

Example:

// seed with a constant
Mt19937 gen;
auto n = gen.front; // same for each run
// Seed with an unpredictable value
gen.seed(unpredictableSeed);
n = gen.front; // different across runs

struct XorshiftEngine(UIntType, UIntType bits, UIntType a, UIntType b, UIntType c) if (isUnsigned!UIntType);

Xorshift generator using 32bit algorithm.

Implemented according to Xorshift RNGs.

bits	period
32	2^32 - 1
64	2^64 - 1
96	2^96 - 1
128	2^128 - 1
160	2^160 - 1
192	2^192 - 2^32

bool isUniformRandom;

Mark this as a Rng

UIntType min;

Smallest generated value.

UIntType max;

Largest generated value.

pure this(UIntType x0);

Constructs a XorshiftEngine generator seeded with x0.

pure nothrow @safe void seed(UIntType x0);

(Re)seeds the generator.

const pure nothrow @property @safe UIntType front();

Returns the current number in the random sequence.

pure nothrow @safe void popFront();

Advances the random sequence.

pure nothrow @property @safe typeof(this) save();

Captures a range state.

const pure nothrow @safe bool opEquals(ref const XorshiftEngine rhs);

Compares against rhs for equality.

alias Xorshift32 = XorshiftEngine!(uint, 32u, 13u, 17u, 15u).XorshiftEngine;
alias Xorshift64 = XorshiftEngine!(uint, 64u, 10u, 13u, 10u).XorshiftEngine;
alias Xorshift96 = XorshiftEngine!(uint, 96u, 10u, 5u, 26u).XorshiftEngine;
alias Xorshift128 = XorshiftEngine!(uint, 128u, 11u, 8u, 19u).XorshiftEngine;
alias Xorshift160 = XorshiftEngine!(uint, 160u, 2u, 1u, 4u).XorshiftEngine;
alias Xorshift192 = XorshiftEngine!(uint, 192u, 2u, 1u, 4u).XorshiftEngine;
alias Xorshift = XorshiftEngine!(uint, 128u, 11u, 8u, 19u).XorshiftEngine;

Define XorshiftEngine generators with well-chosen parameters. See each bits examples of "Xorshift RNGs". Xorshift is a Xorshift128's alias because 128bits implementation is mostly used.

Example:

// Seed with a constant
auto rnd = Xorshift(1);
auto num = rnd.front;  // same for each run

// Seed with an unpredictable value
rnd.seed(unpredictableSeed());
num = rnd.front; // different across runs

@property uint unpredictableSeed();

A "good" seed for initializing random number engines. Initializing with unpredictableSeed makes engines generate different random number sequences every run.

Example:

auto rnd = Random(unpredictableSeed);
auto n = rnd.front;
...

alias Random = MersenneTwisterEngine!(uint, 32LU, 624LU, 397LU, 31LU, 2567483615u, 11LU, 7LU, 2636928640u, 15LU, 4022730752u, 18LU).MersenneTwisterEngine;

The "default", "favorite", "suggested" random number generator type on the current platform. It is an alias for one of the previously-defined generators. You may want to use it if (1) you need to generate some nice random numbers, and (2) you don't care for the minutiae of the method being used.

@property ref Random rndGen();

Global random number generator used by various functions in this module whenever no generator is specified. It is allocated per-thread and initialized to an unpredictable value for each thread.

auto uniform(string boundaries = "[)", T1, T2)(T1 a, T2 b) if (!is(CommonType!(T1, T2) == void));
auto uniform(string boundaries = "[)", T1, T2, UniformRandomNumberGenerator)(T1 a, T2 b, ref UniformRandomNumberGenerator urng) if (isFloatingPoint!(CommonType!(T1, T2)) && isUniformRNG!UniformRandomNumberGenerator);

Generates a number between a and b. The boundaries parameter controls the shape of the interval (open vs. closed on either side). Valid values for boundaries are "[]", "(]", "[)", and "()". The default interval is closed to the left and open to the right. The version that does not take urng uses the default generator rndGen.

Example:

auto gen = Random(unpredictableSeed);
// Generate an integer in [0, 1023]
auto a = uniform(0, 1024, gen);
// Generate a float in [0, 1$(RPAREN)
auto a = uniform(0.0f, 1.0f, gen);

auto uniform(T, UniformRandomNumberGenerator)(ref UniformRandomNumberGenerator urng) if (!is(T == enum) && (isIntegral!T || isSomeChar!T) && isUniformRNG!UniformRandomNumberGenerator);
auto uniform(T)() if (!is(T == enum) && (isIntegral!T || isSomeChar!T));

Generates a uniformly-distributed number in the range [T.min, T.max] for any integral type T. If no random number generator is passed, uses the default rndGen.

auto uniform(E, UniformRandomNumberGenerator)(ref UniformRandomNumberGenerator urng) if (is(E == enum) && isUniformRNG!UniformRandomNumberGenerator);
auto uniform(E)() if (is(E == enum));

Returns a uniformly selected member of enum E. If no random number generator is passed, uses the default rndGen.

Examples:

enum Fruit { apple, mango, pear }
auto randFruit = uniform!Fruit();

T uniform01(T = double)() if (isFloatingPoint!T);
T uniform01(T = double, UniformRNG)(ref UniformRNG rng) if (isFloatingPoint!T && isUniformRNG!UniformRNG);

Generates a uniformly-distributed floating point number of type T in the range [0, 1). If no random number generator is specified, the default RNG rndGen will be used as the source of randomness.

uniform01 offers a faster generation of random variates than the equivalent uniform!"["(0.0, 1.0)) and so may be preferred for some applications.

F[] uniformDistribution(F = double)(size_t n, F[] useThis = null) if (isFloatingPoint!F);

Generates a uniform probability distribution of size n, i.e., an array of size n of positive numbers of type F that sum to 1. If useThis is provided, it is used as storage.

void randomShuffle(Range, RandomGen)(Range r, ref RandomGen gen) if (isRandomAccessRange!Range && isUniformRNG!RandomGen);
void randomShuffle(Range)(Range r) if (isRandomAccessRange!Range);

Shuffles elements of r using gen as a shuffler. r must be a random-access range with length. If no RNG is specified, rndGen will be used.

void partialShuffle(Range, RandomGen)(Range r, in size_t n, ref RandomGen gen) if (isRandomAccessRange!Range && isUniformRNG!RandomGen);
void partialShuffle(Range)(Range r, in size_t n) if (isRandomAccessRange!Range);

Partially shuffles the elements of r such that upon returning r[0..n] is a random subset of r and is randomly ordered. r[n..r.length] will contain the elements not in r[0..n]. These will be in an undefined order, but will not be random in the sense that their order after partialShuffle returns will not be independent of their order before partialShuffle was called.

r must be a random-access range with length. n must be less than or equal to r.length. If no RNG is specified, rndGen will be used.

size_t dice(Rng, Num)(ref Rng rnd, Num[] proportions...) if (isNumeric!Num && isForwardRange!Rng);
size_t dice(R, Range)(ref R rnd, Range proportions) if (isForwardRange!Range && isNumeric!(ElementType!Range) && !isArray!Range);
size_t dice(Range)(Range proportions) if (isForwardRange!Range && isNumeric!(ElementType!Range) && !isArray!Range);
size_t dice(Num)(Num[] proportions...) if (isNumeric!Num);

Rolls a dice with relative probabilities stored in proportions. Returns the index in proportions that was chosen.

Example:

auto x = dice(0.5, 0.5);   // x is 0 or 1 in equal proportions
auto y = dice(50, 50);     // y is 0 or 1 in equal proportions
auto z = dice(70, 20, 10); // z is 0 70% of the time, 1 20% of the time,
                           // and 2 10% of the time

struct RandomCover(Range, UniformRNG = void) if (isRandomAccessRange!Range && (isUniformRNG!UniformRNG || is(UniformRNG == void)));
auto randomCover(Range, UniformRNG)(Range r, auto ref UniformRNG rng) if (isRandomAccessRange!Range && isUniformRNG!UniformRNG);
auto randomCover(Range)(Range r) if (isRandomAccessRange!Range);

Covers a given range r in a random manner, i.e. goes through each element of r once and only once, just in a random order. r must be a random-access range with length.

If no random number generator is passed to randomCover, the thread-global RNG rndGen will be used internally.

Example:

int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8 ];
foreach (e; randomCover(a))
{
    writeln(e);
}

WARNING: If an alternative RNG is desired, it is essential for this to be a new RNG seeded in an unpredictable manner. Passing it a RNG used elsewhere in the program will result in unintended correlations, due to the current implementation of RNGs as value types.

Example:

int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8 ];
foreach (e; randomCover(a, Random(unpredictableSeed)))  // correct!
{
    writeln(e);
}

foreach (e; randomCover(a, rndGen))  // DANGEROUS!! rndGen gets copied by value
{
    writeln(e);
}

foreach (e; randomCover(a, rndGen))  // ... so this second random cover
{                                    // will output the same sequence as
    writeln(e);                      // the previous one.
}

These issues will be resolved in a second-generation std.random that re-implements random number generators as reference types.

struct RandomSample(Range, UniformRNG = void) if (isInputRange!Range && (isUniformRNG!UniformRNG || is(UniformRNG == void)));
auto randomSample(Range)(Range r, size_t n, size_t total) if (isInputRange!Range);
auto randomSample(Range)(Range r, size_t n) if (isInputRange!Range && hasLength!Range);
auto randomSample(Range, UniformRNG)(Range r, size_t n, size_t total, auto ref UniformRNG rng) if (isInputRange!Range && isUniformRNG!UniformRNG);
auto randomSample(Range, UniformRNG)(Range r, size_t n, auto ref UniformRNG rng) if (isInputRange!Range && hasLength!Range && isUniformRNG!UniformRNG);

Selects a random subsample out of r, containing exactly n elements. The order of elements is the same as in the original range. The total length of r must be known. If total is passed in, the total number of sample is considered to be total. Otherwise, RandomSample uses r.length.

RandomSample implements Jeffrey Scott Vitter's Algorithm D (see Vitter 1984, 1987), which selects a sample of size n in O(n) steps and requiring O(n) random variates, regardless of the size of the data being sampled. The exception to this is if traversing k elements on the input range is itself an O(k) operation (e.g. when sampling lines from an input file), in which case the sampling calculation will inevitably be of O(total).

RandomSample will throw an exception if total is verifiably less than the total number of elements available in the input, or if n > total.

If no random number generator is passed to randomSample, the thread-global RNG rndGen will be used internally.

Example:

int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ];
// Print 5 random elements picked off from a
foreach (e; randomSample(a, 5))
{
    writeln(e);
}

WARNING: If an alternative RNG is desired, it is essential for this to be a new RNG seeded in an unpredictable manner. Passing it a RNG used elsewhere in the program will result in unintended correlations, due to the current implementation of RNGs as value types.

Example:

int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ];
foreach (e; randomSample(a, 5, Random(unpredictableSeed)))  // correct!
{
    writeln(e);
}

foreach (e; randomSample(a, 5, rndGen))  // DANGEROUS!! rndGen gets
{                                        // copied by value
    writeln(e);
}

foreach (e; randomSample(a, 5, rndGen))  // ... so this second random
{                                        // sample will select the same
    writeln(e);                          // values as the previous one.
}

These issues will be resolved in a second-generation std.random that re-implements random number generators as reference types.

const @property bool empty();
void popFront();
@property typeof(this) save();
@property size_t length();

Range primitives.

@property size_t index();

Returns the index of the visited record.

Copyright Andrei Alexandrescu 2008 - 2009, Joseph Rushton Wakeling 2012. | Page generated by Ddoc.