Semina più generatori di numeri casuali

Question

Sono stato recentemente discusso l'inizializzazione di più generatori di numeri casuali dello stesso tipo nei commenti di un altro post e in quella discussione abbiamo chiesto le seguenti domande:

1) E 'una buona idea di creare più istanze dello stesso generatore di numeri casuali con semi diversi e utilizzare questi generatori di numeri casuali in diverse parti del programma?

2) In particolare, può la tecnica di creazione di generatori di numeri casuali usando la classe Random Net, seminati come sotto, e utilizzando ogni RNG in differenti contesti programma causare problemi:

int size = 64; // The number of RNGs to use 
int seed;  // Get seed using some normal technique 
Random[] r = new Random[size]; 

for (int i = 0; i < size; i++) 
{ 
    r[i] = new Random(seed + i); 
} 

3) Quale si consiglia invece se sono necessari più flussi di numeri casuali?

4) Come si consiglia di generare numeri casuali quando è richiesta la sicurezza del filo?

Answer 1

1) È una buona idea creare più istanze dello stesso generatore di numeri casuali con semi diversi e utilizzare questi generatori di numeri casuali in diverse parti del programma?

No. In generale, lo schema sopra non è raccomandato.

Nel suo libro The Art of Computer Programming, Volume 2: Algoritmi seminali. Addison-Wesley, Reading, MA, terza edizione, 1997, il Dr. Knuth afferma che

Non è facile inventare una fonte infallibile di numeri casuali.

In questo caso, segnalo che prendere sottosequenze da una sequenza casuale può essere meno casuale rispetto alla sequenza originale di numeri casuali:

• Random Numbers
• PCG

Avviso l'implementazione di Random di Micosoft è basata su un generatore di subractive lagged-fibonacci:

• Reference Source - System.Random

Questo tipo di generatore di numeri casuali è noto per una correlazione a tre punti incorporato, dopo tutto, stiamo generando il prossimo numero casuale:

Questi tipi di Random Number I generatori dipendono anche fortemente dall'inizializzazione del loro stato iniziale di 55 numeri. Una scarsa inizializzazione può portare a numeri casuali scarsi. Nel caso precedente, stati simili, possono risultare in numeri casuali correlati da ciascuno dei diversi generatori di numeri casuali. Microsoft consiglia anche contro questo nel loro posto di MSDN su System.Random: MSDN The System.Random class and thread safety:

Invece di istanziare i singoli oggetti casuali, si consiglia di creare una singola istanza a caso per generare tutti i numeri casuali necessari per la vostra applicazione.

Vedremo un esempio in cui un'inizializzazione particolare crea una forte correlazione tra i diversi generatori di numeri casuali e cerca alternative.

2) Ho implementato un programma che tenta di inizializzare 64 istanze di Random come descritto sopra in modo da osservare eventuali difetti visibili. Ho scelto un particolare inizializzazione come prova di concetto:

int size = 64; // The number of random numbers generators 
int length = 20; // The number of random numbers from each generator 
int steps = 18; // Move 18 steps forward in the beginning to show a particular phenomenon 

Random[] r = new Random[size]; 

for (int i = 0; i < size; i++) 
{ 
    r[i] = new Random(i + 1); 

    // move RNG forward 18 steps 
    for (int j = 0; j < steps; j++) 
    { 
      r[i].Next(3); 
    } 
} 


for (int i = 0; i < size; i++) 
{ 
    for (int j = 0; j < length; j++) 
    { 
      Console.Write(r[i].Next(3) + ", "); // Generate a random number, 0 represents a small number, 1 a medium number and 2 a large number 
    } 

    Console.WriteLine(); 
} 

Questo programma genera l'output mostrato qui, ogni riga rappresenta l'uscita da un altro RNG:

noti che le colonne evidenziati: in particolari luoghi gli RNG sembrano sincronizzarsi e produrre un output che non sembra indipendente l'uno dall'altro.

Vorrei anche aggiungere un'altra nota, che la creazione di un singolo elenco di numeri casuali e l'assunzione di un numero casuale dall'elenco di ogni riga produce anche numeri casuali dall'aspetto povero (l'RNG utilizzato qui è noto per aver fallito qualche statistica Dopotutto!).

3) Il tipo di RNG utilizzato dipende dal contesto. Alcuni potrebbero essere felici con l'output di cui sopra. In altri casi, l'RNG utilizzato potrebbe essere inutilizzabile (Monte Carlo Simulation e Cryptography sono due scenari in cui System.Random deve essere mai, anche per un flusso di numeri casuali).

Se è necessario estrarre più sottosequenze di numeri casuali, trovare un RNG che è stato progettato per questo scopo:

• PCG

4) Infine, che cosa se voglio utilizzare System . Casuale in più thread? Microsoft MSDN ha la risposta nello stesso link di cui ho parlato sopra:

• MSDN The System.Random class and thread safety

Answer 2

Non so cosa sia "più flussi di numeri casuali" si intende. In numeri casuali non esiste alcuna relazione tra due numeri casuali, non c'è un ordine, ognuno è un'istanza autonoma.

Se si utilizza un PRNG crittografico, non è necessario alcun seeding. Si consideri il .net RNGCryptoServiceProvider Class.