C++ Logo


Advanced search

Re: Comments for P0205 and P2060: Mersenne twister can actually generate 7 and 13

From: Lénárd Szolnoki <cpp_at_[hidden]>
Date: Wed, 17 Nov 2021 21:06:57 +0000

On Wed, 17 Nov 2021 18:26:41 +0000
Dimitrij Mijoski via Std-Proposals <std-proposals_at_[hidden]>

> The papers P0205<https://wg21.link/p0205> and
> P2060<https://wg21.link/p2060> like to improve the code for proper
> seeding of the standard Mersenne twister. Both papers cite the
> following article
> https://www.pcg-random.org/posts/cpp-seeding-surprises.html by
> Melissa O’Neill. I will start with that article and their claim that
> the standard Mersenne twister (std::mt19937) can never produce some
> integers on the first call after seeding. In particular, the numbers
> 7 are 13 are mentioned. I state that such claim is false with a
> simple counterexample in code.
> #include <random>
> #include <cassert>
> using namespace std;
> int main()
> {
> auto rnd = mt19937(1080100664);
> assert(rnd() == 7);
> rnd = mt19937(736640520);
> assert(rnd() == 7);
> rnd = mt19937(1292535796);
> assert(rnd() == 13);
> }

Consider the following code:

#include <random>

using gen = std::mt19937;
using res_t = gen::result_type;

res_t foo(res_t x) {
    gen g(x);
    return g();

`foo` is a pure function. You demonstrated that foo(1080100664) ==
foo(736640520) == 7 . Since the range and domain are the same finite
sets, it follows that there must be some number that can never be the
return value of `foo`.

I don't know how the author of the original article made the mistake,
but the point still stands: there are some numbers that can never occur
as the first number from a generator seeded from a single number,
unless a function similar to `foo` above happens to be a bijection for
the given generator.

I don't think that this is a reasonable assumption for any generator, so
I don't see it as a critique of Mersenne-Twister, rather it's a critique
of the improper seeding method.

Whether this seeding method is appropriate or not is yet an other
concern. Even if I agree that it is, there still should be a generic
way to properly seed a generator. The current seed sequence way to do
it is unnecessarily cumbersome and AFAIK there is no way to make it
generic over the generator type.


Received on 2021-11-17 15:07:07