为什么linear_congruential_engine :: seed(Sseq)会丢弃种子序列生成的三个数字？

Question

C++标准(从C++ 11到当前的C++ 17草案的所有方式)在[rand.eng.lcong]中说明如下:

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

效果:构造一个linear_congruential_engine对象.与ķ =⌈log ₂(米)÷32⌉和一个长度的阵列32(或等效物)ķ + 3,调用q.generate(a + 0, a + k + 3),然后计算小号 =(Σ _{Ĵ = 0} ^{ķ -1} 一个_{Ĵ 3} ·2 ^{32 Ĵ})mod m.如果c mod m为0且S为0,则将引擎状态设置为1,否则将引擎状态设置为S.

为什么一个₀,一个₁和一个₂丢弃？

Answer 1

这是我自己一直试图弄清楚的事情。我有一个假设，但没有真正的证据。然而，该规则起源于的文档（由 @TC 链接的N2079 ）证实了我的部分理论。

\n\n

请注意，规则来源的函数接受std::seed_seq文档中的对象，而不是模板化类。这意味着在编写规则时，它是专门为 制定的std::seed_seq，而不是一般的 SeedSequence 概念。这意味着我们可以查看该类std::seed_seq以获取有关此信息的信息，特别是如何std::seed_seq::generate定义的信息。

\n\n

使用的方法在 cppreference.com 上std::seed_seq::generate有很好的解释。虽然有点复杂，但是可以概括为4个阶段。

\n\n

\n

1. 使用一些初始数据初始化输出范围（我包括k=0在这里）

\n

2. 将原始种子数据移至输出范围 ( k=1..s)

\n

3. 将种子数据扩展到输出范围的其余部分（k=s+1..m-1其中m=max(s+1, n)）

\n

4. k=m..m+n-1对输出范围 ( )中的数据进行打乱

\n

\n\n

当std::linear_congruential_engine用模 <= 2 ³²（包括std::minstd_rand和std::minstd_rand0）播种 a 时，它应该只需要从 生成 1 个值std::seed_seq，但根据此规则，它会生成 4。那么当n从 1 变为 4 时，该算法会发生什么变化？

\n\n

变化的一部分是洗牌阶段从 1 次迭代变为 4 次。由于目标之一std::seed_seq是产生高质量的种子值“给定一个小种子或分布不良的初始种子序列。”，这些额外的洗牌迭代可能会改进结果种子值。它删除前 3 个值而不是最后一个值的原因是因为后面的值（通常）是被打乱得更多的值。

\n\n

还值得注意的是，所有 4 个阶段的关键方程是值begin[k]^begin[k+p]^begin[k\xe2\x88\x921]（最后阶段将 XOR 替换为加法）。当 时n=1，这只是变成begin[k]（或3*begin[k]对于最后阶段）（请注意“输出范围的索引begin[x]以 n 为模”和x % 1 == 0）。当 时n=4，该方程更像其预期的那样，这有助于更有效地调整数据。

\n\n

因此，简短的答案是std::linear_congruential_engine丢弃由种子序列生成的 3 个数字，因为生成std::seed_seq这些数字可以提高其实际使用的值的质量。现在，在生成器中丢弃这些数字的决定是在定义 SeedSequence 的通用概念之前决定的，因此在生成器中解决问题更有意义，而不是使种子序列类过于复杂。然而，这现在意味着任何种子序列生成的前 3 个值都将被丢弃。这是否值得可能还有争议，但现在就是这样。

\n