lundi 13 novembre 2017

Which C++ random number engines have a O(1) discard function?

Since C++11 there are a number of std randon 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://ift.tt/1I7X3QP)

However, on www.cppreference.com (http://ift.tt/2iaoS8f) there is a note to say that

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

How do I know for which engines the actual cost of discard is O(1)?




Aucun commentaire:

Enregistrer un commentaire