mir.random.engine.splitmix

pure nothrow @nogc @safe ulong fmix64(ulong m1, ulong m2, uint shift1, uint shift2, uint shift3)(ulong x);

64-bit MurmurHash3-style bit mixer, parameterized.

Pattern is:

ulong fmix64(ulong x)
{
    x = (x ^ (x >>> shift1)) * m1;
    x = (x ^ (x >>> shift2)) * m2;
    return x ^ (x >>> shift3);
}

As long as m1 and m2 are odd each operation is invertible with the consequence that fmix64(a) == fmix64(b) if and only if (a == b).

Good parameters for fmix64 are found empirically. Several sets of suggested parameters are provided.

template murmurHash3Mix()

template staffordMix01()

template staffordMix02()

template staffordMix03()

template staffordMix04()

template staffordMix05()

template staffordMix06()

template staffordMix07()

template staffordMix08()

template staffordMix09()

template staffordMix10()

template staffordMix11()

template staffordMix12()

template staffordMix13()

template staffordMix14()

Well known sets of parameters for fmix64. Predefined are murmurHash3Mix and staffordMix01 through staffordMix14.

See David Stafford's 2011 blog entry Better Bit Mixing - Improving on MurmurHash3's 64-bit Finalizer.

Examples:

enum ulong x1 = murmurHash3Mix(0x1234_5678_9abc_defeUL);//Mix some number at compile time.
static assert(x1 == 0xb194_3cfe_a4f7_8f08UL);

immutable ulong x2 = murmurHash3Mix(0x1234_5678_9abc_defeUL);//Mix some number at run time.
assert(x1 == x2);//Same result.

Examples:

//Verify all sets of predefined parameters are valid
//and no two are identical.
ulong[15] array;
array[0] = murmurHash3Mix(1);
array[1] = staffordMix01(1);
array[2] = staffordMix02(1);
array[3] = staffordMix03(1);
array[4] = staffordMix04(1);
array[5] = staffordMix05(1);
array[6] = staffordMix06(1);
array[7] = staffordMix07(1);
array[8] = staffordMix08(1);
array[9] = staffordMix09(1);
array[10] = staffordMix10(1);
array[11] = staffordMix11(1);
array[12] = staffordMix12(1);
array[13] = staffordMix13(1);
array[14] = staffordMix14(1);
foreach (i; 1 .. array.length)
    foreach (e; array[0 .. i])
        if (e == array[i])
            assert(0, "fmix64 predefines are not all distinct!");

alias SplitMix64 = SplitMixEngine!(staffordMix13, false).SplitMixEngine;

Canonical fixed increment (non-splittable) SplitMix64 engine.

64 bits of state, period of 2 ^^ 64.

Examples:

import mir.random;
static assert(isSaturatedRandomEngine!SplitMix64);
auto rng = SplitMix64(1u);
ulong x = rng.rand!ulong;
assert(x == 10451216379200822465UL);

Examples:

import mir.random;
import std.range.primitives: isRandomAccessRange;
// SplitMix64 should be both a Mir-style saturated
// random engine and a Phobos-style uniform RNG
// and random access range.
static assert(isPhobosUniformRNG!SplitMix64);
static assert(isRandomAccessRange!SplitMix64);
static assert(isSaturatedRandomEngine!SplitMix64);

SplitMix64 a = SplitMix64(1);
immutable ulong x = a.front;
SplitMix64 b = a.save;
assert (x == a.front);
assert (x == b.front);
assert (x == a[0]);

immutable ulong y = a[1];
assert(x == a());
assert(x == b());
assert(a.front == y);

alias Splittable64 = SplitMixEngine!(staffordMix13, true).SplitMixEngine;

Canonical splittable (specifiable-increment) SplitMix64 engine.

128 bits of state, period of 2 ^^ 64.

Examples:

import mir.random;
static assert(isSaturatedRandomEngine!Splittable64);
auto rng = Splittable64(1u);
ulong x = rng.rand!ulong;
assert(x == 10451216379200822465UL);

//Split example:
auto rng1 = Splittable64(1u);
auto rng2 = rng1.split();

assert(rng1.rand!ulong == 17911839290282890590UL);
assert(rng2.rand!ulong == 14201552918486545593UL);
assert(rng1.increment != rng2.increment);

Examples:

import mir.random;
import std.range.primitives: isRandomAccessRange;
// Splittable64 should be both a Mir-style saturated
// random engine and a Phobos-style uniform RNG
// and random access range.
static assert(isPhobosUniformRNG!Splittable64);
static assert(isRandomAccessRange!Splittable64);
static assert(isSaturatedRandomEngine!Splittable64);

Splittable64 a = Splittable64(1);
immutable ulong x = a.front;
Splittable64 b = a.save;
assert (x == a.front);
assert (x == b.front);
assert (x == a[0]);

immutable ulong y = a[1];
assert(x == a());
assert(x == b());
assert(a.front == y);

enum ulong DEFAULT_SPLITMIX_INCREMENT;

alias GOLDEN_GAMMA = DEFAULT_SPLITMIX_INCREMENT;

Default increment used by SplitMixEngine. Defined in Fast Splittable Pseudorandom Number Generators (2014) as "the odd integer closest to (2 ^^ 64)/φ, where φ = (1 + √5)/2 is the golden ratio." In the paper this constant is referred to as "GOLDEN_GAMMA".

From the authors:

[...] our choice of the odd integer closest to (2 ^^ 64)/φ was based only on the intuition that it might be a good idea to keep γ values “well spread out” and the fact that prefixes of the Weyl sequence generated by 1/φ are known to be “well spread out” [citing vol. 3 of Knuth's The Art of Computer Programming, exercise 6.4-9]

struct SplitMixEngine(alias mixer, bool split_enabled = false, OptionalArgs...) if ((__traits(compiles, () { static assert(__traits(isSame, TemplateOf!(mixer!()), fmix64)); } ) || __traits(compiles, () { static assert(__traits(isSame, TemplateOf!mixer, fmix64)); } )) && (OptionalArgs.length < 1 || is(typeof(OptionalArgs[1]) == ulong) && (OptionalArgs[1] != DEFAULT_SPLITMIX_INCREMENT)) && (OptionalArgs.length < 2));

Generic SplitMixEngine.

The first parameter mixer should be a explicit instantiation of fmix64 or a predefined parameterization of fmix64 such as murmurHash3Mix or staffordMix13.

The second parameter is whether the split operation is enabled. Allows each instance to have a distinct increment, increasing the size from 64 bits to 128 bits. If split is not enabled then the opCall, seed, and skip operations will be shared provided the platform supports 64-bit atomic operations.

The third parameter is the default_increment. If the SplitMixEngine has a fixed increment this value will be used for each instance. If omitted this parameter defaults to DEFAULT_SPLITMIX_INCREMENT.

Examples:

//Can specify engine like this:
alias RNG1 = SplitMixEngine!staffordMix13;
alias RNG2 = SplitMixEngine!(fmix64!(0xbf58476d1ce4e5b9UL, 0x94d049bb133111ebUL, 30, 27, 31));

//Each way of writing it results in the same sequence.
assert(RNG1(1).opCall() == RNG2(1).opCall());

//However not each result's name is equally informative.
static assert(RNG1.stringof == `SplitMixEngine!(staffordMix13, false)`);
static assert(RNG2.stringof == `SplitMixEngine!(fmix64, false)`);//Doesn't include parameters of fmix64!

enum ulong default_increment;

Either DEFAULT_SPLITMIX_INCREMENT or the optional third argument of this template.

enum bool isRandomEngine;

Marks as a Mir random engine.

enum ulong max;

Largest generated value.

enum uint period_pow2;

Full period (2 ^^ 64).

enum bool increment_specifiable;

Whether each instance can set its increment individually. Enables the split operation at the cost of increasing size from 64 bits to 128 bits.

ulong state;

Current internal state of the generator.

ulong increment;

alias gamma = increment;

Either an enum or a settable value depending on whether increment_specifiable == true. This should always be an odd number. The paper refers to this as γ so it is aliased as gamma.

this()(ulong x0);

Constructs a SplitMixEngine generator seeded with x0.

this()(ulong x0, ulong increment)
if (increment_specifiable);

Constructs a SplitMixEngine generator seeded with x0 using the specified increment.

Note from the authors (the paper uses γ to refer to the increment):

[W]e tested PRNG objects with “sparse” γ values whose representations have either very few 1-bits or very few 0-bits, and found that such cases produce pseudorandom sequences that DieHarder regards as “weak” just a little more often than usual.

As a consequence the provided split function guards against this and also against increments that have long consecutive runs of either 1 or 0. However, this constructor only forces increment to be an odd number and performs no other transformation.

ulong opCall()();

shared ulong opCall()()
if (!increment_specifiable);

Advances the random sequence.

Examples:

auto rnd = SplitMixEngine!staffordMix13(1);
assert(rnd() == staffordMix13(1 + GOLDEN_GAMMA));

typeof(this) split()()
if (increment_specifiable);

Produces a splitmix generator with a different counter-value and increment-value than the current generator. Only available when increment_specifiable == true.

Examples:

auto rnd1 = SplitMixEngine!(staffordMix13,true)(1);
auto rnd2 = rnd1.split();
assert(rnd1.state != rnd2.state);
assert(rnd1.increment != rnd2.increment);
assert(rnd1() != rnd2());

void skip()(size_t n);

shared void skip()(size_t n)
if (!increment_specifiable);

Skip forward in the random sequence in Ο(1) time.

enum bool isUniformRandom;

enum ulong min;

enum bool empty;

const @property ulong front()();

void popFront()();

void seed()(ulong x0);

shared void seed()(ulong x0)
if (!increment_specifiable);

void seed()(ulong x0, ulong increment)
if (increment_specifiable);

const @property typeof(this) save()();

const ulong opIndex()(size_t n);

size_t popFrontN()(size_t n);

template popFrontExactly()

Compatibility with Phobos library methods. Presents this RNG as an InputRange.