Boost Mersenne Twister: comment les graines avec plus d'une valeur?

Question

J'utilise la mise en œuvre de mt19937 boost pour une simulation.

La simulation doit être reproductible, et que les moyens de stockage et potentiellement réutilisant les graines de RNG plus tard. J'utilise la api de Windows pour générer les valeurs de départ parce que je besoin d'une source externe pour les graines et non en raison des garanties particulières de hasard. La sortie de une séance de simulation aura une note dont la graine de RNG - si la graine doit être raisonnablement court . D'autre part, dans le cadre de l'analyse de la simulation, je comparerai plusieurs pistes - mais pour être sûr que ces pistes sont en fait différents, je vais avoir besoin d'utiliser différentes graines - donc les besoins en semences à être suffisamment longue pour éviter les collisions accidentelles .

J'ai déterminé que 64 bits de semis devraient suffire; la possibilité d'une collision atteindra 50% après environ 2 ^ 32 pistes - cette probabilité est suffisamment faible pour que l'erreur moyenne causée par elle est négligeable pour moi. En utilisant seulement 32 bits de semences est délicate; la possibilité d'une collision atteint 50% déjà après 2 ^ 16 pistes; et c'est un peu trop sans doute à mon goût.

Malheureusement, la mise en œuvre de boost soit les graines avec un plein vecteur d'état - ce qui est beaucoup, beaucoup trop long - ou un 32 bits unsigned long - qui n'est pas idéal

.

Comment puis-je interroger le générateur avec plus de 32 bits, mais moins d'un vecteur complet de l'État? J'ai essayé juste padding le vecteur ou répéter les graines pour remplir le vecteur d'état, mais même un coup d'œil sur les résultats montre que qui génère des résultats médiocres.

Answer 1

Vos hypothèses sont erronées. Pour une simulation, vous n'avez pas besoin de graines cryptographiquement forte. En fait, en utilisant les graines 1,2,3,4, etcetera est souvent une meilleure idée. Les valeurs de sortie du Mersenne Twister sera décorrélé, mais personne ne demande si vous cerise cueillies vos graines pour obtenir des sorties de simulation souhaitées.

Pour d'autres personnes qui ont un réel besoin des valeurs, un moyen facile est de jeter les premières (graines) >> 32 générés. Cela vous donne environ log2 (graines) >> 32 bits supplémentaires de l'État. Cependant, il ne fonctionne que si vous avez besoin efficacement quelques bits supplémentaires. Ajout de 32 bits de cette façon est probablement trop lent.

Un algorithme plus rapide est de générer le plein vecteur d'état pour le bien générateur aléatoire. Les solutions mentionnées dans la question (stroboscopique ou le rembourrage) ne sont pas si bon en raison du caractère aléatoire limitée dans le vecteur d'état résultant. Mais si vous remplissez le vecteur d'état initial de la sortie de mersenne_twister(seed1) ^ mersenne_twister(seed2), ce n'est pas un problème du tout.

Answer 2

Regarder sources d'amplification du modèle mersenne_twister :

  void seed(UIntType value)
  {
    // New seeding algorithm from 
    // http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html
    // In the previous versions, MSBs of the seed affected only MSBs of the
    // state x[].
    const UIntType mask = ~0u;
    x[0] = value & mask;
    for (i = 1; i < n; i++) {
      // See Knuth "The Art of Computer Programming" Vol. 2, 3rd ed., page 106
      x[i] = (1812433253UL * (x[i-1] ^ (x[i-1] >> (w-2))) + i) & mask;
    }
  }

Pour mt19937 UIntType est uint32_t, w est 32. Pour les semences de 64 bits, vous pourriez peut-être utiliser les 32 bits inférieurs pour calculer tous les indices même de l'état (x) et les 32 bits supérieurs pour calculer les indices impairs de la état, en utilisant cet algorithme.

(Ceci est la suggestion de culte du cargo si)