C++ Logo


Advanced search

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

From: Jason McKesson <jmckesson_at_[hidden]>
Date: Tue, 23 Nov 2021 23:28:29 -0500
On Tue, Nov 23, 2021 at 5:23 PM Dimitrij Mijoski via Std-Proposals
<std-proposals_at_[hidden]> wrote:
> On Mon, 2021-11-22 at 13:03 -0500, Arthur O'Dwyer via Std-Proposals wrote:
> Correct. I think you misunderstood the point of my message. I'm not saying that "specifying a number of bits to take from random_device, and then 'key-stretching' those into a larger seed value suitable for MT19937," a.k.a. "under-seeding MT19937," is a good operation nor that any working programmer should ever want to do it. I'm just saying that if you wanted to do it, then you could easily do it via an intermediate PRNG that takes a seed of the proper size.
> What you call "underseeding" and key-stretching is the default way of working. What you call "fully seeding" with 624 integers is a new and unexplored land. There is a reason for that. Let's look at the original implementation from 2002. There are two initialization functions, one that accepts a 32-bit integer, and another that accepts a sequence of arbitrary length. Not 624, but arbitrary, can be less can be more. That function does not copy directly the seeding sequence, instead it does a lot of bit manipulation. That is because there are some initial states that are unwanted. From what I read, states with lot of consecutive zeroes are unwanted initial states. No matter what size is the seed, the initialization routines avoid some states. Thus the total number of initial states is not (2^32)^624 but is something less. Therefore, not any PRNG can be used to do the "stretching". The standard C++ MT19937 has this protection in the constructor that that takes seed sequence, and that should remain there.

The SSeq constructor for MT is explicitly defined to generate a
specific number of integers, sufficient to fill up the state. It
generates no less and no more than that, no matter what their values
are. The generated values are copied directly into the internal state.

The MT constructor is defined to do some fiddling with the state in
certain isolated circumstances, but it never *generates* more data.
Nor is the SSeq required to provide any particular mechanism for
generating bits. So whatever "this protection" is, it has nothing to
do with the *mechanism* used to generate those bits.

So yes, *any RNG engine* can be used to do the stretching, if it
provides the SSeq interface. The SSeq interface is not *required* to
be implemented by `seed_seq`.

Received on 2021-11-23 22:28:42