c++ - 哪些 C++ 随机数引擎具有 O(1) 丢弃函数？

Question

从 C++11 开始，有许多标准随机数引擎。他们实现的成员函数之一是 void discard(int long long z)跳过 z 随机生成的数字。该函数的复杂度在 www.cplusplus.com ( http://www.cplusplus.com/reference/random/mersenne_twister_engine/discard/ ) 上给出为 O(z)

但是，在 www.cppreference.com ( http://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine/discard ) 上有一条注释说

For some engines, "fast jump" algorithms are known, which advancing the state by many steps (order of millions) without calculating intermediate state transitions.

我怎么知道哪些引擎的实际丢弃成本是 O(1)？

Answer 1

好吧，如果您使用预先计算的跳转点，O(1) 将适用于现有的每个 RNG。请记住，有些算法可能比 O(z) 更好，但不是 O(1) - 例如，O(log2 z)。

如果我们谈论跳转到任意点，事情就会变得有趣。例如，对于 linear congruential generator有已知的 O(log2 z) 跳转算法，基于 F. Brown 的论文，“随机数生成与任意步幅”，Trans。是。核。社会。 (1994 年 11 月)。代码示例是 here .

C++11 标准中有 LCG RNG，不确定在特定实现中跳转的速度有多快(http://en.cppreference.com/w/cpp/numeric/random/linear_congruential_engine)

PCG family的 RNG 共享相同的属性，我相信