Semina di generatori di numeri casuali multipli

Recentemente ho discusso dell’inizializzazione di più generatori di numeri casuali dello stesso tipo nei commenti di un altro post e in quella discussione abbiamo posto le seguenti domande:

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?

2) In particolare, la tecnica di creazione di generatori di numeri casuali che utilizzano la class Random .Net, seminata come di seguito e l’utilizzo di ciascun RNG in diversi contesti di programma, causa 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) Cosa consiglieresti invece se sono richiesti più flussi di numeri casuali?

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

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 lo afferma

Non è facile inventare una fonte infallibile di numeri casuali.

In questo caso, sottolineo che prendere sequenze da una sequenza casuale può essere meno casuale della sequenza originale di numeri casuali:

  • Numeri casuali
  • PCG

Si noti che l’implementazione di Random di Micosoft è basata su un generatore di fibroacci ritardato subractive:

  • Fonte di riferimento – System.Random

Questo tipo di generatore di numeri casuali è noto per una correlazione a tre punti incorporata, dopotutto, stiamo generando il prossimo numero casuale: Subtractive Lagged-Fibonacci Generator

Questi tipi di generatori di numeri casuali 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 post MSDN su System.Random: MSDN The System.Random class and thread safety :

Invece di creare istanze di singoli oggetti casuali, ti consigliamo di creare una singola istanza Casuale per generare tutti i numeri casuali necessari all’app.

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 una particolare inizializzazione come prova del 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'output di un altro RNG:

Uscita del programma

Si noti che le colonne evidenziate: in particolari punti, gli RNG sembrano sincronizzarsi e produrre output che non sembrano indipendenti gli uni dagli altri.

Vorrei anche aggiungere un'altra nota, che creare un singolo elenco di numeri casuali e prendere un numero casuale dall'elenco di ogni riga produce anche numeri casuali dall'aspetto povero (il RNG usato qui è noto per aver fallito qualche statistica dopo tutto!) .

3) Il tipo di RNG utilizzato dipende dal tuo 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 non dovrebbe mai essere utilizzato, anche per un stream di numeri casuali).

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

  • PCG

4) Infine, cosa succede se voglio usare System.Random in più thread? Microsoft MSDN ha la risposta nello stesso collegamento a cui ho fatto riferimento sopra:

  • MSDN The System.Random di class e sicurezza thread

Non sei sicuro di cosa significhi “più flussi di numeri casuali”. 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 eseguire il seeding. Considerare la class .net RNGCryptoServiceProvider .