Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 4 down vote favorite

I'm attempting to use the MT19937 variant of the Mersenne Twister PRNG to accomplish something. Whether or not this something is feasible depends upon the answers to these two questions:

What is the greatest value of m for which the following statements hold true:

1 - For all seed values, the algorithm eventually produces every integer list of length m.

2 - There exists a seed value for which the algorithm would eventually produce a given integer list of length m.

share|improve this question
This is in general hard to answer. If you explained your application to us, it might make it easier for us to help you. For 2, $m$ is bounded by the size of the key. If you wanted an algorithm with these two properties for given $m$, you can use a running counter initialized at the seed value. – Yuval Filmus Jan 5 at 6:20
@YuvalFilmus Would you please link to a source or else explain how you know that "for 2, m is bounded by the size of the key"? – sweetname Jan 5 at 6:40
Ah - sorry, I missed the "eventually" part. – Yuval Filmus Jan 5 at 7:03
Well, Wikipedia says that this PRG has a period of $2^{19937}−1$, so, assuming 32 bit integers that gives us an upper bound $m \leq \frac{\ln (2^{19937}−1)}{32 \ln 2} \approx 623$. At first I wrongly assumed that the sequences can't overlap and using Lambert W got $m \leq 622$. It's weird how little difference this made... – Karolis Juodelė Jan 5 at 21:03

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.