哪些C ++随机数引擎具有O（1）丢弃功能？ [英] Which C++ random number engines have a O(1) discard function?
问题描述
自C ++ 11起，有许多标准随机数引擎。他们实现的成员函数之一是 void throws（int long long z），它跳过z个随机生成的数字。此函数的复杂性在www.cplusplus.com上以O（z）表示（ http ：//www.cplusplus.com/reference/random/mersenne_twister_engine/discard/ ）
Since C++11 there are a number of std random number engines. One of the member functions they implement is void discard(int long long z) which skips over z randomly generated numbers. The complexity of this function is given as O(z) on www.cplusplus.com (http://www.cplusplus.com/reference/random/mersenne_twister_engine/discard/)
不过，请访问www.cppreference.com（ http://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine/discard ）中有一条注释要说明，即
However, on www.cppreference.com (http://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine/discard) there is a note to say that
对于某些引擎，已知快速跳转算法，该算法使$ b前进$ b可以通过许多步骤（数百万个阶次）来计算状态，而无需计算
中间状态转换。
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）？
How do I know for which engines the actual cost of discard is O(1)?
推荐答案
那么，如果您使用预先计算的跳转点，则O（1 ）将适用于现有的每个RNG。请记住，有些算法可能比O（z）更好，但不是O（1）-例如，O（log 2 z）。
Well, if you use precomputed jump points, O(1) will work for each and every RNG in existence. Please, remember, that there are algorithm which might have better than O(z), but not O(1) - say, O(log2 z).
如果我们正在谈论跳到任意点，事情将会变得有趣。例如，对于线性同余生成器，已知O（log 2 z）跳前算法，基于F. Brown的论文，任意步幅生成随机数，Trans。上午。核仁Soc。 （1994年11月）。代码示例为此处。
If we're talking about jump to arbitrary point, things get interesting. For example, for linear congruential generator there is known O(log2 z) jump ahead algorithm, based upon paper by F. Brown, "Random Number Generation with Arbitrary Stride," Trans. Am. Nucl. Soc. (Nov. 1994). Code example is here.
在C ++ 11标准中有LCG RNG，不确定在特定的实现中前进有多快（ http://en.cppreference.com/w/cpp/numeric/random/linear_congruential_engine ）
There is LCG RNG in the C++11 standard, not sure how fast jump ahead is done in particular implementation (http://en.cppreference.com/w/cpp/numeric/random/linear_congruential_engine)
PCG family of RNGs share the same property, I believe
这篇关于哪些C ++随机数引擎具有O（1）丢弃功能？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
