Which C ++ random number engines have an O (1) drop function?

Question

Since C ++ 11, there are several std blocks of random numbers. One of the member functions that they implement is void discard(int long long z) , which skips z randomly generated numbers. The complexity of this function is set as O (z) at www.cplusplus.com ( http://www.cplusplus.com/reference/random/mersenne_twister_engine/discard/ )

However, at www.cppreference.com ( http://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine/discard ) there is a note to say that

For some engines, fast transition algorithms are known that state in several steps (in the order of millions) without calculating intermediate state transitions.

How do you know for which engines the actual discharge cost is O (1)?

Answer 1

Well, if you use precomputed jump points, O (1) will work for every existing RNG. Please remember that there is an algorithm that may be better than O (z), but not O (1) - let's say O (log ₂ z).

If we talk about jumping to an arbitrary point, everything becomes interesting. For example, for a linear congruent generator, there is a well-known algorithm for moving forward (log ₂ z), based on a paper by F. Brown, “Generating random numbers with an arbitrary step,” Am. Nucl. Soc. (November 1994). Sample code here .

There is LCG RNG in C ++ 11 standard, not sure if fast forward is performed in a specific implementation ( http://en.cppreference.com/w/cpp/numeric/random/linear_congruential_engine )

The PCG family of RNGs have the same property, I suppose