Implements the C++11 standard library mersenne_twister_engine
with
absolutely no dependence on any other header files.
Also has some extended functionality.
// Use exactly like std::mt19937 (It generates the same numbers)
using mt19937 = freestanding_mersenne_twister::mt19937<>;
// Likewise for std::mt19937_64
using mt19937_64 = freestanding_mersenne_twister::mt19937_64<>;
operator>>
/operator<<
are different, see below. But they should not be used and replaced with manipulatingstate()
. These were implementation defined to begin with, but you should still be able to use it with libstdc++'sstd::mersene_twister_engine<...>
.- All functions (except
operator>>
/operator<<
) are nowconstexpr
in C++14 and up. mt19937<>
is a template alias with some at-least 32 bit integer type by default. The standard library version would bemt19937<std::uint_fast32_t>
, which is grossly inefficient ifuint_fast32_t
is 64 bit since the state array would double in size.- Similar for
mt19937_64<>
, with some at-least 64 bit integer type instead ofstd::uint_fast64_t
.
namespace freestanding_mersenne_twister {
template<class UIntType, size_t w, size_t n, size_t m, size_t r, UIntType a, size_t u, UIntType d, size_t s, UIntType b, size_t t, UIntType c, size_t l, UIntType f>
struct mersenne_twister_engine;
template<class UInt32 = /* smallest 32+ bit type out of unsigned short, unsigned and unsigned long */>
using mt19937 =
mersenne_twister_engine<UInt32, 32, 624, 397, 31,
0x9908'b0dfu, 11, 0xffff'ffffu, 7, 0x9d2c'5680u, 15, 0xefc6'0000u, 18, 1'812'433'253u>;
template<class UInt64 = /* smallest 64+ bit type out of unsigned short, unsigned, unsigned long and unsigned long long */>
using mt19937_64 =
mersenne_twister_engine<UInt64, 64, 312, 156, 31,
0xb502'6f5a'a966'19e9u, 29, 0x5555'5555'5555'5555u, 17,
0x71d6'7fff'eda6'0000u, 37, 0xfff7'eee0'0000'0000u, 43, 6'364'136'223'846'793'005u>;
}
mt19937<T>
, where T
is an integral type that has a bit width of 32 or greater,
is an engine which produces the same sequence as std::mt19937
.
mt19937_64<T>
is the same with an at-least 64 bit integral type and std::mt19937_64
.
No exceptions are thrown by the engine itself but operations on arguments passed in might throw (for example, inserting into a stream or incrementing an iterator).
(Constructor that takes a seed sequence and seed function that do the same only exist
if the macro FREESTANDING_MERSENNE_TWISTER_NO_SEED_SEQUENCE
is not defined before
including the header the first time. These are not documented and work as you expect)
result_type
: The template parameterUIntType
. This is the type of the value generated by the engine. It must be an unsigned integral type.state_type
:mersenne_twister_engine
inherits from this types. It is an aggregate typemersnne_twister_state<result_type, state_size>
that stores the current state of the engine (see below).
// Constructors
constexpr mersenne_twister_engine() noexcept : mersenne_twister_engine(default_seed) {}
constexpr explicit mersenne_twister_engine(result_type value) noexcept;
/* implicitly-declared */ constexpr mersenne_twister_engine(const mersenne_twister_engine&) noexcept = default;
constexpr explicit mersenne_twister_engine(const state_type& state) noexcept;
The integer used to construct a mersenne_twister_engine
(defaulting to default_seed
)
seeds the random sequence. Any two mersenne_twister_engine
s constructed with the same
seed are equal (i.e., will produce the same sequence of numbers).
The implicitly-declared copy constructor is trivial and will produce a mersenne_twister_engine
equal to its argument.
If constructed from a state, the underlying state will be equal to the passed in state.
Equivalent to this->state() = state;
.
// Copy-assign
/* implicitly-declared */ constexpr mersenne_twister_engine& operator=(const mersenne_twister_engine&) noexcept = default;
mersenne_twister_engine
objects are trivially copyable: This copies each element of the state,
including the index i
. *this
will subsequently be equal to the argument passed in.
constexpr void seed(result_type value = default_seed) noexcept;
Equivalent to *this = mersenne_twister(value);
. The sequence will be from the beginning.
constexpr result_type operator()() noexcept;
template<class InputIt, class Sentinel = InputIt>
constexpr InputIt operator()(InputIt first, Sentinel last) noexcept(/*if possible*/);
The first overload advances the state of the engine and returns the next value.
The second overload writes successive values while advancing the state, similar to
std::ranges::generate(first, last, *this)
, but more efficiently.
This takes (amortised) O(1)
time for each number generated (so the second overload
is O(std::ranges::distance(first, last))
).
constexpr result_type peek(unsigned long long distance = 0) const noexcept;
template<class InputIt, class Sentinel = InputIt>
constexpr InputIt peek(InputIt first, Sentinel last, unsigned long distance = 0) const noexcept (/*if possible*/);
The first overload will return what calling operator()
would do after calling
operator()
distance
times without actually changing the state of *this
.
The second overload does the same except it writes to the range [first, last) what
successive invocations of operator()
would return.
peek(0)
takes O(1)
time. For any other value, it takes O(distance + state_size)
time.
The second overload takes O(distance + std::ranges::distance(first, last) + state_size)
time.
constexpr void discard(unsigned long long z) noexcept;
Equivalent to calling operator()
z
times and discarding the results: Efficiently
advances the state of the generator z
times.
friend constexpr bool operator==(const mersenne_twister_engine&, const mersenne_twister&) noexcept;
In C++23, this is trivial and just compares each member of the state and the index.
Before that, this emualates that (comparing each object in the array in the state and
then the index), and an operator!=
is provided too that returns the negation of this.
When two mersenne_twister_engine
objects are equal, they will generate the same
sequence of random numbers.
template<class OStream>
friend OStream& operator<<(OStream& os, const mersenne_twister_engine& x);
template<class IStream>
friend IStream& operator>>(IStream& is, mersenne_twister_engine& x);
This is one function that diverges from std::mersenne_twister_engine
. Since the
definition of std::basic_ostream
/std::basic_istream
isn't available, a generic
placeholder is used. When actually called, these should be a basic_ostream
/basic_istream
.
Will output each element of the state array seperated by a space, followed by the current index.
Will input something in the same format.
Reading the characters previously written to a stream will produce an equal
mersenne_twister_engine
. However, it is more efficient to directly serialize
the bytes of the state of the engine (taking care with byte order if it is
going to be read on a different system).
constexpr const state_type& state() const &;
constexpr state_type& state() &;
Returns the aggregate type holding the entire state of *this
.
static constexpr result_type scramble(result_type x) noexcept;
Scrambles the argument according to the parameters given in the template arguments.
This is the function called on all members of the state before returning them
(i.e., e.peek() == decltype(e)::scramble(e.X[e.i])
).
static constexpr result_type min() noexcept { return 0; }
static constexpr result_type max() noexcept {
// (numeric_limits not actually used, this is for illustration purposes)
using limits = std::numeric_limits<result_type>;
return word_size == limits::digits ? limits::max() : (result_type(1) << word_size) - result_type(1);
}
The range of the produced values (inclusive). max()
returns the value of 2word_size
-1,
guarding against overflow in the power.
result_type X[state_size];
:state_size
word_size
bit integers, used to produce each random number as well as the next state.size_t i;
: An index wherei < state_size
which decides which of the elements ofX
is going to produce the next number. Increments after calls tooperator()
and others, set to0
after it reachesstate_size
.
static constexpr size_t word_size;
: The template parameterw
.static constexpr size_t state_size;
: The template parametern
.static constexpr size_t shift_size;
: The template parameterm
.static constexpr size_t mask_bits;
: The template parameterr
.static constexpr result_type xor_mask;
: The template parametera
.static constexpr size_t tempering_u;
: The template parameteru
.static constexpr result_type tempering_d;
: The template parameterd
.static constexpr size_t tempering_s;
: The template parameters
.static constexpr result_type tempering_b;
: The template parameterb
.static constexpr size_t tempering_t;
: The template parametert
.static constexpr result_type tempering_c;
: The template parameterc
.static constexpr size_t tempering_l;
: The template parameterl
.static constexpr result_type initialization_multiplier;
: The template parameterf
.static constexpr result_type default_seed;
: A constant,5489u
.
namespace freestanding_mersenne_twister {
}
// A trivial aggregate type
template<class UIntType, size_t n>
struct mersenne_twister_state {
using result_type = UIntType;
static constexpr size_t state_size = n;
result_type X[state_size];
size_t i;
};
}
X
and i
are described above. mersenne_twister_engine<UIntType, n, ...>
inherits from
mersenne_twister_state<UIntType, n>
to get its data members X
and i
.
No protection is provided if these are set incorrectly. It is undefined behaviour if
a member function of mersenne_twister_engine
is called and i >= state_size
.
If a elements of X
is out of range of word_size
, the numbers generated may also be
greater than word_size
, but the behaviour is otherwise not undefined.
There are also non-member functions operator==
and operator<<
/operator>>
that work the same as there corresponding versions in mersenne_twister_engine
.
using mt19937 = freestanding_mersenne_twister::mt19937<>;
using mt19937_64 = freestanding_mersenne_twister::mt19937_64<>;
static_assert(mt19937{}.peek(10000) == 4123659995u);
static_assert(mt19937_64{}.peek(10000) == 9981545732273789042u);
int main() {
mt19937_64 e(1234);
(void) e();
auto x = e();
auto y = e.peek();
auto z = e();
assert(y == z);
mt19937_64 e2;
e2.seed(1234);
e2.discard(1);
unsigned long xy[2];
e2(xy, xy + 2);
assert(xy[0] == x && xy[1] == y);
auto e3 = e2;
assert(e3 == e2 && e3() == e2());
write_to_file("path/to/file.bin", reinterpret_cast<const char*>(&e3.state()), sizeof(e3.state()));
mt19937_64 e4;
read_from_file("path/to/file.bin", reinterpret_cast<char*>(&e4.state()), sizeof(e4.state()));
assert(e3 == e4 && e3() == e4());
}