Why does linear_congruential_engine :: seed (Sseq) discard the three numbers generated by the seed sequence?

Question

The C ++ standard (all the way from C ++ 11 to the current C ++ 17 project) says the following in [rand.eng.lcong]:

template<class Sseq> explicit linear_congruential_engine(Sseq& q); 

Effects: Creates a linear_congruential_engine object. With k = ⌈log ₂ (m) ÷ 32⌉ and an array 32 (or equivalent) of length k + 3 calls q.generate(a + 0, a + k + 3) , and then calculates S = (Σ _{j = 0} ^{k -1} a _{j + 3} · 2 ^{32 j} ) mod m. If c mod m is 0 and S is 0, sets the state of the engines 1, otherwise the state of the engines is set to S.

Why are ₀ , a ₁ and ₂ discarded?

Answer 1

This is what I tried to figure out myself. I had a hypothesis, but there was no real evidence for this. However, a rule arose in the document ( N2079 , associated with @TC) It confirmed part of my theory.

Note that the function from which the rule is executed takes the std::seed_seq in the document, not the template class. This means that when the rule was written, it was made specifically for std::seed_seq , and not for the concept of SeedSequence in general. This means that we can look at the std::seed_seq to get information about this, in particular, how std::seed_seq::generate determined.

The method that uses std::seed_seq::generate is well explained at cppreference.com . This is a bit complicated, but it can be summarized in 4 steps.

• Initialize the output range with some raw data (here I include k=0 )

• Move the seed source data to the output range ( k=1..s )

• Expand the seed data in the rest of the output range ( k=s+1..m-1 where m=max(s+1, n) )

• Shuffle data into output range ( k=m..m+n-1 )

When sowing a std::linear_congruential_engine with a module <= 2 ³² (which includes std::minstd_rand and std::minstd_rand0 ), it should only generate 1 value from std::seed_seq , but with this rule it generates 4. So , what are the changes in this algorithm when changing n from 1 to 4?

One of the changes is that the shuffling step goes from 1st iteration to 4. Since one of the goals of std::seed_seq is to get high-quality sowing values ​​“based on a small number of seeds or a poorly distributed initial seed sequence”, these additional shuffles iterations are likely to improve the resulting seed value. The reason it falls out of the first three values ​​instead of the last is because later values ​​(usually) are those that are shuffled more.

It is also worth noting that the key equation of all 4 stages is the value begin[k]^begin[k+p]^begin[k−1] (when replacing XOR with the addition at the last stage). When n=1 , it just becomes begin[k] (or 3*begin[k] for the last stage) (note that "indexing the output range begin[x] taken modulo n" and x % 1 == 0 ) . When n=4 , this equation works more like the way it was intended, which helps randomly move data.

So the short answer is that std::linear_congruential_engine discards 3 numbers generated by the seed sequence, since std::seed_seq generates these numbers, improves the quality of the values ​​it uses. Now the decision to drop these numbers in the generator was made before the general concept of SeedSequence was defined, so it was more reasonable to solve the problem in the generator, rather than overly complicating the seed sequence class. However, now this means that the first 3 values ​​generated by the seed sequence any are discarded. Whether or not it’s worth it is probably debatable, but it’s the way it is now.