1. Takie, które generują liczby w pewnym cyklu, którego długość znamy. Generator po pewnym czasie się zapętla i generuje jeszcze raz te same liczby w tej samej kolejności. Każde ziarno (seed) znajduje się w cyklu.
2. Takie które bazują na losowych permutacjach (patrz: random permutation statistics, wikipedia), funkcja, która jest w generatorze po wprowadzeniu do niej liczb \(\displaystyle{ 1,2,3,...}\) tworzy pewną permutację (pseudolosową). W przypadku takiego generatora, jeżeli zainicjujemy go jakimś ziarnem nie znamy długości cyklu, taka losowa permutacja ma bowiem kilka cykli o różnej długości i nie wiemy na jaki cykl trafimy. Możemy to natomiast szacować, potrafimy policzyć spodziewaną długość cyklu.
3. Takie, które bazują na tzw. random non-invertible mappings (czyli chyba możemy to przetłumaczyć jako losowe nieodwracalne odwzorowania - możemy generować liczby "w przód", a nie ma jednego sposobu w jaki możemy się cofać w generatorze, taki generator może bazować na nieodwracalnych arytmetycznie operacjach, jak np. mnożenie przez liczbę nieparzystą modulo \(\displaystyle{ 2^{n}}\)):
Kod: Zaznacz cały
www.pcg-random.org/posts/random-invertible-mapping-statistics.html
Po to, żeby nie mieć problemu ze zbyt krótkimi cyklami generatorów PRNG niektórzy posłużyli się pewnym schematem. Historycznie bodajże pierwszy zrobił to George Marsaglia w "Xorshift RNGs". Do stanu generatora o pewnej długości cyklu \(\displaystyle{ 2^{n}-1}\) dodał on tzw. Weyl sequence. Weyl sequece to po prostu sekwencja liczb obliczania według wzoru:
\(\displaystyle{ w_{n+1} = w_{n} + s}\)
gdzie \(\displaystyle{ s}\) to jakaś stała. W praktyce ze względu na skończoną precyzję różnych typów zmiennych oblicza się:
\(\displaystyle{ w_{n+1} = (w_{n} + s) \mod 2^{m}}\)
I sekwencja ma cykl o długości \(\displaystyle{ 2^{m}}\). Jeżeli mamy jakiś generator, który oblicza stan \(\displaystyle{ x}\) za pomocą funkcji \(\displaystyle{ f(x)}\), to w kolejnym kroku dodajemy lub xorujemy weyl sequence z \(\displaystyle{ x}\):
Kod: Zaznacz cały
x = f(x)
weyl = weyl + s
x = x + weyl
Kod: Zaznacz cały
arxiv.org/pdf/1704.00358.pdf
Kod: Zaznacz cały
uint64_t x = 0, w = 0, s = 0xb5ad4eceda1ce2a9;
inline static uint32_t msws32()
{
x *= x;
x += (w += s);
return x = (x>>32) | (x<<32);
}
Moje pytanie dotyczy tego ile wynosi długość ścieżki do cyklu i cyklu w tak zbudowanym generatorze? Moje doświadczenia z generatorem Middle-Square Weyl ze zmniejszonym stanem wskazują, że ścieżka do cyklu nadal wynosi \(\displaystyle{ \sqrt {\pi \cdot \frac {N}{8}}}\), natomiast sama długość cyklu, gdy generator już w niego wpadnie wynosi tyle co długość cyklu Weyl sequence. Ale, czy to na sens? Jak to udowodnić?
Mam też drugi problem. Mam jeszcze bardziej skomplikowany generator stworzony przeze mnie, działa on podobnie:
Kod: Zaznacz cały
{
k = k + x;
x = f(x,k);
x += (w += s);
}
Ponadto pytanie, czy, jeśli rozpatrzymy sobie zmodyfikowany generator Widynskiego:
Kod: Zaznacz cały
uint64_t x = 0, k = 123, w = 0, s = 0xb5ad4eceda1ce2a9;
inline static uint32_t msws32()
{
k += x;
x *= x;
x += (w += s);
return x = (x>>32) | (x<<32);
}