Jak mogę określić okres mojego generatora liczb pseudolosowych?

14

Załóżmy, że używam liniowego kongruencjalnego generatora liczb pseudolosowych (PRNG). Biorąc pod uwagę ziarno , mnożnik (a), współczynnik przesunięcia (c) i współczynnik modułu (m), jak mogę określić okres mojego PRNG? Czy ustalam to za pomocą algorytmów eksperymentów / wykrywania wzorców, czy też istnieje bezpośredni wzór na obliczenie jego okresu? x0

Chociaż moje pytanie dotyczy konkretnie liniowej metody przystającej, jestem otwarty na więcej informacji na temat tego, jak okresy są obliczane w praktyce również dla innych PRNG.

random-number-generation Paweł
źródło
Odpowiedni: en.wikipedia.org/wiki/…
BTW, jeśli używasz LFSR, to okres jest maksymalny, jeśli wielomian sprzężenia zwrotnego jest prymitywny . W takim przypadku okres AFAIK (nie cytuj mnie; zbyt leniwy, aby wykopać notatki z kursu) to gdzie wielomian sprzężenia zwrotnego z stopień , a jest wielkością pola współczynników. p ( x ) ∈ F q [ x ] n qqnp(x)∈Fq[x]nq
2
Algorytmy wykrywania cyklu Floyda, a także algorytmy wykrywania cyklu Brenta są skutecznymi sposobami wykrywania cykli. Oba zwrócą kilka wielokrotności L okresu, a kiedy już to zrobisz, możesz podzielić L na czynniki i zobaczyć, który jest najmniejszym czynnikiem, który jest kropką.
xdavidliu

Odpowiedzi:

12

Jeśli ograniczasz się do pełnego cyklu LCG PRNG, odpowiedź jest łatwa, z definicji jest to po prostu .m

Aby znaleźć okres niepełnego cyklu PRG dla LCG dla danego materiału siewnego, wystarczy policzyć liczbę iteracji PRNG, aż ponownie wygeneruje wartość materiału siewnego.

Z przywołanej strony wikipedii :

Długość okresu

Okres ogólnej LCG jest co najwyżej , a dla niektórych wyborów znacznie mniej. Pod warunkiem, że jest niezerowe, LCG będzie miało pełny okres dla wszystkich wartości nasion, jeśli i tylko jeśli :mc

  • c i są względnie pierwsze ,m
  • a−1 można podzielić przez wszystkie czynniki pierwszemm
  • a−1 jest wielokrotnością 4, jeśli jest wielokrotnością 4.m

Podczas gdy LCG są w stanie wytwarzać przyzwoite liczby pseudolosowe , jest to niezwykle wrażliwe na wybór parametrów , oraz .cma

Historycznie złe wybory doprowadziły do ​​nieskutecznych wdrożeń LCG. Szczególnie ilustrującym tego przykładem jest RANDU, który był szeroko stosowany na początku lat siedemdziesiątych i doprowadził do wielu wyników, które są obecnie kwestionowane z powodu zastosowania tego słabego LCG.

Dlaczego chcesz użyć generatora pełnego cyklu

Jeśli nie ograniczysz się do pełnego cyklu PRNG LCG, podejmujesz ogromne ryzyko .

Jeśli nie wiesz, że dany LCG ma pełny cykl, możesz skończyć z generatorem o dowolnej liczbie wzajemnie różnych sekwencji, z których niektóre mogą być żenująco małe i mieć przerażającą losowość, być może nawet gorszą niż niesławny generator RANDU .

Naprawdę nie chcesz sprawdzać każdej możliwej wartości początkowej, aby upewnić się, że generuje ona sekwencję wystarczająco długą dla twojej aplikacji.

Dalsza lektura

Aby uzyskać doskonały starter na pseudolosowych generatorach liczb, zdecydowanie polecam przeczytanie rozdziału Przepisy liczbowe na temat liczb losowych.

Mark Booth
źródło
To prawda, ale nie ograniczam się do pełnych okresów LCG PRNG ... Jestem ciekawy złych wyborów a, c i m, takich, że losowe strumienie, które nie osiągają pełnego okresu. Chciałbym być w stanie wiedzieć z wyprzedzeniem, biorąc pod uwagę a, c i m, jaki nieuchronnie będzie ten okres. Wiem, że górna granica jest ograniczona przez m, ale zastanawiałem się, czy możemy to zrobić lepiej i uzyskać dokładny okres.
Paweł
Nie sądzę, żeby to w ogóle dzieliło włosy na techniczność: pytanie brzmiało „jak ustalić okres LCG o dowolnych parametrach”, podczas gdy ta odpowiedź mówi „nie używaj arbitralnych LCG, zawsze używaj pełnych okresów LCG, i zakładając, że tak , odpowiedź na twoje pytanie byłaby z definicji maksymalnym możliwym okresem ”. Przedstawiony w tej odpowiedzi argument przemawiający za zastosowaniem LCF w pełnym okresie jest całkowicie przekonujący, ale problem polega na tym, że w ogóle nie o to pytano.
xdavidliu
Przepraszam @xdavidliu, ale nie widzę, jak twój nowy komentarz pomaga mi poprawić odpowiedź. Zwróciłeś moją uwagę, że tak naprawdę nie odpowiedziałem na pytanie, zredagowałem moją odpowiedź, aby to naprawić, a następnie poinformowałem cię w sposób, który - jak sądziłem - może sprawić, że się uśmiechniesz (jeśli jesteś fanem Futurama). Nie sądzę, że trzeba coś więcej powiedzieć.
Mark Booth,
Zauważ, że przy wymianie stosu komentarze nie są przeznaczone do długich dyskusji, w tym przypadku wykorzystują czat naukowy . Komentarze mają na celu pomoc w poprawianiu pytań i odpowiedzi oraz rozpraszają uwagę, dlatego staramy się ograniczyć je do minimum. Komentarze należy uważać za efemeryczne, każdy komentarz, który nie pomaga już aktywnie poprawiać pytania lub odpowiedzi, można usunąć w dowolnym momencie, aby uporządkować post.
Mark Booth,