Mersenne Twister - c'è un modo per passare a uno stato particolare?

Question

Sono un po 'incerti circa il forum giusto per questa domanda. E 'tra i comp teorica. sci./math e programmazione.

Io uso Mersenne-Twister per generare pseudo numeri casuali. Ora, a partire da un dato seme, vorrei passare al numero n-esimo nella sequenza.

Ho visto questo: http://www-personal.umich.edu/ ~ wagnerr / MersenneTwister.html , e uno schema potrebbe essere il seguente:

Supponiamo, ho solo il primo N numeri della sequenza casuale completo dalla particolare seme s .
bisogno Ho diviso la sequenza in su p sottosuccessioni, marcia attraverso tutti i numeri N e salvare il vettore di stato del generatore di numeri casuali, all'inizio di ogni sottosequenza.
Ora di accedere a n numero esimo, farò in modo che n cade nel k subsequence esimo e io ti caricare il vettore di stato per questo sottosequenza e generare m numeri casuali consecutivi in ??cui m-esimo numero k-esima sottosequenza è uguale a n-esimo numero della sequenza completa (n = m + (k-1) * n / p).

Ma il vettore di stato è lungo 624 x 4 byte! Mi domando se è praticamente possibile saltare ad un elemento arbitrario nella sequenza generata Mersenne-twister.

Answer 1

Sì, è possibile! Si chiama salto in avanti .

È possibile trovare tutti i dettagli per fare questo con Mersenne Twister sulla homepage degli autori di MT. Codice è disponibile così come le pubblicazioni scientifiche che spiegano l'algoritmo:

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

Answer 2

Oggi, c'è un modo per farlo utilizzando scarto . La complessità è lineare nel numero di acconti equivalenti.

Un esempio di lavoro:

  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

Il Mersenne Twister può essere rappresentato come una (piuttosto grande) matrice sopra (il campo contenente i due elementi 0 e 1) F ₂ . Una transizione allo stato successivo è una moltiplicazione per questa matrice.

Per passare qualche posizione arbitraria nel flusso è possibile calcolare la corrispondente potenza di questa matrice da ripetuti squadratura, e moltiplicarlo con il suo stato iniziale.

Answer 4

Penso che quello che stai chiedendo sarebbe contro la definizione di un generatore di numeri casuali crittograficamente sicuro, così purtroppo non credo che sia possibile.