Siew Wiele liczb losowych Generatory

Question

Niedawno zostały Omawiając inicjalizacji wielu generatorów liczb losowych tego samego typu w komentarzach innym poście i w tej dyskusji poprosiliśmy następujące pytania:

1) jest to dobry pomysł utworzenia wielu wystąpień tego samego generatora liczb losowych z różnych nasion i korzystania z tych generatorów liczb losowych w różnych częściach programu?

2) W szczególności może technika tworzenia generatorów losowych numer za pomocą Random klasy .NET, rozstawiony jak poniżej, a przy użyciu każdego RNG w różnych kontekstach programowych powodować problemy:

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) Co by polecasz zamiast tego, jeśli potrzebujesz wielu strumieni liczb losowych?

4) Jak poleciłbyś generowanie liczb losowych, gdy wymagane jest bezpieczeństwo gwintów?

Answer 1

1) Czy warto utworzyć wiele wystąpień tego samego generatora liczb losowych z różnymi nasionami i użyć tych generatorów liczb losowych w różnych częściach programu?

Nie. Powyższy schemat ogólnie nie jest zalecany.

W swojej książce The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, Reading, MA, wydanie trzecie, 1997, Dr Knuth stwierdza, że ​​

Nie jest łatwo wymyślić niezawodne źródło liczb losowych.

W tym przypadku, wskazują, że przy podsekwencje od kolejności losowej może być mniej losowe niż oryginalna sekwencja liczb losowych:

• Random Numbers
• PCG

Zawiadomienie że implementacja losowa Micosoft opiera się na subraktywnym opóźnionym generatorze fibonacci:

• Reference Source - System.Random

Ten rodzaj generatora liczb losowych jest znany wbudowanym trzypunktowym korelacji, mimo wszystko, jesteśmy generowania następnego liczbę losową:

tego rodzaju Random Number Generatory również w dużej mierze polegają na inicjalizacji ich początkowego stanu liczbowego 55. Słaba inicjalizacja może prowadzić do złych liczb losowych. W powyższym przypadku podobne stany mogą skutkować skorelowanymi liczbami losowymi z każdego z różnych generatorów liczb losowych. Microsoft nawet zaleca się przed tym w swoim poście o System.Random MSDN: MSDN The System.Random class and thread safety:

Zamiast uruchamianiu indywidualnych przypadkowych przedmiotów, zalecamy, aby utworzyć jeden Losowa wystąpienie do generowania liczb losowych wszystkich potrzebnych aplikacji.

Przyjrzymy się przykładowi, w którym konkretna inicjalizacja tworzy silną korelację między różnymi generatorami liczb losowych i szuka alternatyw.

2) Zaimplementowałem program, który próbuje zainicjować 64 wystąpienia Losowego, jak opisano powyżej, aby zaobserwować wszelkie widoczne wady. Wybrałam konkretny inicjalizacji jako dowód pojęcia:

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(); 
} 

Ten program generuje wyjście pokazany tutaj, każdy wiersz reprezentuje wyjście z innego RNG:

Uwaga, wyróżnionych kolumnach: w poszczególnych miejscach wydaje się, że RNG synchronizują się i wytwarzają produkty, które nie wyglądają na niezależne od siebie.

Chciałbym dodać jeszcze jedną uwagę, że utworzenie pojedynczej listy liczb losowych i wzięcie jednej losowej liczby z listy każdego rzędu również powoduje powstanie źle wyglądających liczb losowych (użycie tutaj RNG jest znane z niepowodzenia niektórych statystyk po wszystkim!).

3) Rodzaj używanego RNG zależy od kontekstu. Niektórzy mogą być zadowoleni z powyższego wyniku. W innych przypadkach używany RNG może być bezużyteczny (Symulacja Monte Carlo i Kryptografia to dwa scenariusze, w których System.Random powinien być użyty jako nigdy, nawet dla jednego strumienia liczb losowych).

Jeśli trzeba wyodrębnić wiele krótsze sekwencje liczb losowych, znaleźć RNG, który został zaprojektowany do tego celu:

• PCG

4) Wreszcie, co zrobić, jeśli chcę korzystać z systemu .Random w wielu wątkach? Microsoft MSDN ma odpowiedź w tym samym łączu I, o którym mowa powyżej:

• MSDN The System.Random class and thread safety

Answer 2

nie wiesz, co „wielu strumieni liczb losowych” oznacza. W liczbach losowych nie ma związku między dowolnymi dwiema liczbami losowymi, nie ma porządku, każda jest samodzielną instancją.

Jeśli używasz kryptograficznego PRNG, nie jest wymagane obsiewanie. Rozważmy .net RNGCryptoServiceProvider Class.