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.

  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 5 '13 at 6:20
  • $\begingroup$ @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"? $\endgroup$ – sweetname Jan 5 '13 at 6:40
  • $\begingroup$ Ah - sorry, I missed the "eventually" part. $\endgroup$ – Yuval Filmus Jan 5 '13 at 7:03
  • $\begingroup$ 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... $\endgroup$ – Karolis Juodelė Jan 5 '13 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.