Mersenne Twister - est-il un moyen de passer à un état particulier?

Question

Je suis un peu incertain sur le bon forum pour cette question. Il est entre comp théorique. sci./math et de la programmation.

J'utilise Mersenne-Twister pour générer des nombres pseudo aléatoires. Maintenant, à partir d'une graine donnée, je voudrais sauter au nombre de n-ième dans la séquence.

J'ai vu ceci: http://www-personal.umich.edu/ ~ wagnerr / MersenneTwister.html , et un système pourrait être comme suit:

Supposons, je dois seulement le premier N numéros dans la séquence aléatoire complète à partir de graines particulière .
Je partage la séquence pour p sousséquences, mars à tous les numéros N et enregistrez le vecteur d'état du générateur de nombres aléatoires au début de chaque séquence.
Maintenant, pour atteindre n Numéro -ème, je veillerai à ce que n tombe dans la k -ème et je vais séquence charger le vecteur d'état pour cette sous-séquence et générer m nombres aléatoires consécutifs où le m-ième nombre de k-ième sous-séquence est le même que le n-ième nombre dans la séquence complète (n = m + (k-1) * N / p).

Mais le vecteur d'état est de 624 x 4 octets! Je me demande s'il est pratiquement possible de passer à un élément arbitraire dans la séquence générée Mersenne-Twister.

Answer 1

Oui, il est possible! Il est appelé Aller en avant .

Vous pouvez trouver tous les détails de le faire avec Mersenne Twister sur la page d'accueil des auteurs de MT. Code est disponible ainsi que des publications scientifiques expliquant l'algorithme:

http: // www .math.sci.hiroshima-u.ac.jp / ~ m-mat / MT / JUMP / index.html

Answer 2

Aujourd'hui, il y a une façon de le faire en utilisant défausse . La complexité est linéaire en nombre de progrès équivalents.

Un exemple de travail:

  std::mt19937 engine(0);
  std::uniform_int_distribution<int> dis(0, 9);
  auto generator = std::bind(std::ref(dis), std::ref(engine));

  qDebug() << "First sequence: ";
  for (int i = 0; i < 20; i++) {
    qDebug() << "Random value: " << generator();
  }

  engine.seed(0); // reset
  engine.discard(15); // discard the first 15 numbers from the first sequence
  qDebug() << "Last five numbers from first sequence: ";
  for (int i = 0; i < 5; i++) {
    qDebug() << "Random value: " << generator();
  }

Answer 3

Le Twister Mersenne peut être représenté comme une matrice (plutôt large) sur F ₂ (le champ contenant les deux éléments 0 et 1). Une transition vers l'état suivant est une multiplication par cette matrice.

Pour passer à une position arbitraire dans le flux, vous pouvez calculer la puissance correspondante de cette matrice en élevant au carré répété, et multipliez-le avec votre état initial.

Answer 4

Je pense que ce que vous demandez serait contraire à la définition d'un générateur de nombres aléatoires sécurisé, donc, malheureusement, je ne pense pas qu'il soit possible.