Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania.

[[e-mail]]

Znalazłem ostatnio generator liczb pseudolosowych, który mnie interesuje:

https://en.wikipedia.org/wiki/Permuted_congruential_generator

Ale nie jestem w stanie zrozumieć kodu, który jest tam podany. To jest zdaje się w języku C:

1. count = (int)(x >> 122)
2. low64 = rotr64((uint64_t)(x ^ (x >> 64)), count)
3. high64 = rotr((uint64_t)(x >> 64), low64 & 63)
4. return (uint128_t)high64 << 64 | low64

Jedyne co rozumiem to ">>", "^" i "&". Ale czym jest "int"? Czy to (int)(x >> 122) mam rozumieć jako mnożenie dwóch liczb w nawiasach? Co robi rotr64 i czym się różni od rotr? Co to jest uint64_t? Co to jest "|" i jako rozumieć (uint128_t)high64 << 64 | low64?

Czy ktoś coś z tego rozumie? Nie znam C i nie jestem pewien, czy to jest kod w C, czy coś jeszcze innego.

[Mateusz Viste]

Post by ***@gmail.com
1. count = (int)(x >> 122)
2. low64 = rotr64((uint64_t)(x ^ (x >> 64)), count)
3. high64 = rotr((uint64_t)(x >> 64), low64 & 63)
4. return (uint128_t)high64 << 64 | low64
Jedyne co rozumiem to ">>", "^" i "&". Ale czym jest "int"? Czy to
(int)(x >> 122) mam rozumieć jako mnożenie dwóch liczb w nawiasach?

To zwyczajny casting, tj "włóż wynik x >> 122 do rejestra o szerokości
inta". Głównie służy do tego, żeby kompilator nie krzyczał, że
próbujesz włożyć __uin128_t do inta.

Post by ***@gmail.com
Co robi rotr64 i czym się różni od rotr?

rotr64 operuje na zmiennych 64-bitowych, a rotr na zmiennych o
szerokości inta. W zależności od platformy może wyjść na to samo.

Post by ***@gmail.com
Co to jest uint64_t?

Zmienna zawierająca nieujemną liczbę całkowitą o szerokości 64 bitów.

Post by ***@gmail.com
Co to jest "|" i jako rozumieć (uint128_t)high64 << 64 | low64?

To jest budowanie liczby 128-bitowej z dwóch 64-bitowych "połówek". A
sam "|" to po prostu OR.

Post by ***@gmail.com
Czy ktoś coś z tego rozumie? Nie znam C i nie jestem pewien, czy to
jest kod w C, czy coś jeszcze innego.

C, jak najbardziej.


Mateusz

[[e-mail]]

1. count = (int)(x >> 122)

Czyli "int" to nasza liczba startowa, na której stosujemy ">>"? A może wrzucamy do generatora liczbę x? Skąd wziąć zatem wartość int i czym ona jest?

Post by Mateusz Viste
rotr64 operuje na zmiennych 64-bitowych, a rotr na zmiennych o
szerokości inta. W zależności od platformy może wyjść na to samo.

Post by ***@gmail.com
Co to jest uint64_t?

Zmienna zawierająca nieujemną liczbę całkowitą o szerokości 64 bitów.

A skąd mam wziąć wartość tej zmiennej? Wstawiam do równania uint64_t, ale ile to ma konkretnie wynosić? A może to:

((uint64_t)(x ^ (x >> 64)

to wcale nie jest mnożenie, tylko chodzi o coś innego? Ja tu widzę pomnóż liczbę uint64_t razy (x ^ (x >> 64).

[[e-mail]]

Post by Mateusz Viste
rotr64 operuje na zmiennych 64-bitowych, a rotr na zmiennych o
szerokości inta. W zależności od platformy może wyjść na to samo.

A jaką szerokość może mieć int? Rozumiem, że większą niż 64 bity? Po co używać tego zamiennie? Rozumiem, że rotr zrobiłoby to samo co rotr64?

[Mateusz Viste]

Post by ***@gmail.com

Post by Mateusz Viste
rotr64 operuje na zmiennych 64-bitowych, a rotr na zmiennych o
szerokości inta. W zależności od platformy może wyjść na to samo.

A jaką szerokość może mieć int?

wg. ISO 9899-1990, int ma co najmniej 16 bitów. Górnej granicy brak. Na
obecnych platformach to w praktyce 32 albo 64 bity.

Post by ***@gmail.com
Rozumiem, że większą niż 64 bity?

Być może takie platformy istnieją. Ja się nie spotkałem.

Post by ***@gmail.com
Po co używać tego zamiennie? Rozumiem, że rotr zrobiłoby to samo co
rotr64?

Tylko na platformie, na której int ma 64 bity.

Mateusz

[[e-mail]]

Może napiszę jak ja to rozumiem na chłopski rozum.

1. count = (int)(x >> 122)

Weź jakąś 128-bitową liczbę startową X i zrób right shift o 122 miejsca. 6 najbardziej znaczących bitów trafia w miejsce najmniej znaczących i wychodzi nam jakaś mała 6-bitowa liczba. Swoją drogą dlaczego autor wymyślił tego shifta akurat o 122 bity (być może z jakichś powodów daje najlepsze wyniki)?

2. low64 = rotr64((uint64_t)(x ^ (x >> 64)), count)

Oblicz pierwszą połówkę jako low64. Najpierw policz X XOR X >> 64. Wychodzi mi tu 128-bitowa liczba, ale rozumiem, że uint64_t zawęża ją tylko do 64 najmniej znaczących bitów? Teraz liczymy na niej rotr64 z przesunięciem o count.

3. high64 = rotr((uint64_t)(x >> 64), low64 & 63)

Tu liczymy wyższą połówkę. Tutaj otrzymujemy 64-bitową liczbę poprzez X >> 64 i robimy na niej rotr. Nadal nie rozumiem dlaczego nie możemy tu zrobić i zapisać również rotr64? Czy operacja X >> 64 nie zawsze da nam liczbę 64-bitową? Gdyby X było powiedzmy liczbą 84 bitową, to >> 64 zrobi z niej liczbę 20-bitową. Czyli wtedy nie możemy zrobić rotr64 (bo nie mamy 64 bitów)? A właściwie możemy, ale otrzymamy inny wynik, niż rotr na liczbie 20-bitowej. Jedynie takie widzę tu uzasadnienie.

4. return (uint128_t)high64 << 64 | low64

Tutaj rozumiem, że robimy shift na high64 i doklejamy do tego low64? low64 to będą bity najmniej znaczące.

[Mateusz Viste]

Post by ***@gmail.com
Może napiszę jak ja to rozumiem na chłopski rozum.
1. count = (int)(x >> 122)
Weź jakąś 128-bitową liczbę startową X i zrób right shift o 122
miejsca. 6 najbardziej znaczących bitów trafia w miejsce najmniej
znaczących i wychodzi nam jakaś mała 6-bitowa liczba.

Zgadza się. I tutaj, zakładając, że count zostało wcześniej zdefiniowane
jako int, kompilator może się poskarżyć "uważaj, bo próbujesz przypisać
zmienną 128-bitową (x) do zmiennej o mniejszej szerokości (count)".
Dlatego programista wykonuje cast wyniku do (int), aby powiedzieć
kompilatorowi "spokojnie, wiem co robię, to naprawdę ma być int".

Post by ***@gmail.com
Swoją drogą dlaczego autor wymyślił tego shifta akurat o 122 bity
(być może z jakichś powodów daje najlepsze wyniki)?

To już należałoby jego zapytać. Ew. poczytać publikacje dot. tego
algorytmu.

Post by ***@gmail.com
2. low64 = rotr64((uint64_t)(x ^ (x >> 64)), count)
Oblicz pierwszą połówkę jako low64. Najpierw policz X XOR X >> 64.
Wychodzi mi tu 128-bitowa liczba, ale rozumiem, że uint64_t zawęża ją
tylko do 64 najmniej znaczących bitów?

Tak. 64 najbardziej znaczące bity zostają usunięte, za sprawą castu
(castingu? nie mam pewności jak to się mówi po polskiemu) do uint64_t.

Post by ***@gmail.com
Teraz liczymy na niej rotr64 z przesunięciem o count.

Warto tu zaznaczyć, że rotr64 to nie C. Po nazwie mogę tylko
przypuszczać, co robi, ale dla pełnej jasności należałoby doczytać
dokumentację danej implementacji.

Post by ***@gmail.com
3. high64 = rotr((uint64_t)(x >> 64), low64 & 63)
Tu liczymy wyższą połówkę. Tutaj otrzymujemy 64-bitową liczbę poprzez
X >> 64 i robimy na niej rotr. Nadal nie rozumiem dlaczego nie możemy
tu zrobić i zapisać również rotr64?

Też nie wiem. Tym bardziej, że autor wyszczególnił cast do uint64_t, a
prototyp rotr() który podaje mi google wskazuje że rotr() oczekuje
inta. Nie mam pewności, co autor miał na myśli, ale wygląda mi to na
pomyłkę.

Post by ***@gmail.com

Post by ***@gmail.com
Gdyby X było powiedzmy liczbą 84 bitową, to
64 zrobi z niej liczbę 20-bitową. Czyli wtedy nie możemy zrobić
rotr64 (bo nie mamy 64 bitów)? A właściwie możemy, ale otrzymamy
inny wynik, niż rotr na liczbie 20-bitowej. Jedynie takie widzę tu
uzasadnienie.

Na platformie, na której sizeof(int) == 8, wynik będzie identyczny w
obu przypadkach.

Post by ***@gmail.com
4. return (uint128_t)high64 << 64 | low64
Tutaj rozumiem, że robimy shift na high64 i doklejamy do tego low64?
low64 to będą bity najmniej znaczące.

Tak. A cast do uint128_t jest tutaj konieczny, bo bez niego high64
by się po prostu wyzerował (wyshiftował).

Mateusz

[[e-mail]]

Znalazłem coś takiego na stronie autora:

https://www.pcg-random.org/download.html#c-implementation

#if PCG_HAS_128BIT_OPS
inline pcg128_t pcg_output_xsl_rr_rr_128_128(pcg128_t state)
{
uint32_t rot1 = (uint32_t)(state >> 122u);
uint64_t high = (uint64_t)(state >> 64u);
uint64_t low = (uint64_t)state;
uint64_t xored = high ^ low;
uint64_t newlow = pcg_rotr_64(xored, rot1);
uint64_t newhigh = pcg_rotr_64(high, newlow & 63u);
return (((pcg128_t)newhigh) << 64u) | newlow;
}
#endif

Wygląda na to, że chodzi o dwa razy o rotr64 i faktycznie na wikipedii jest błąd lub niedopatrzenie.

[Mateusz Viste]

Post by ***@gmail.com
1. count = (int)(x >> 122)
Czyli "int" to nasza liczba startowa, na której stosujemy ">>"? A
może wrzucamy do generatora liczbę x? Skąd wziąć zatem wartość int i
czym ona jest?

int to nie jest żadna wartość, to tylko informacja dla kompilatora:
"wynik obliczenia (x >> 122) ogranicz do tylu bitów, ile ma normalny
int na tym systemie". Czyli typowo (dziś) 32 albo 64. W tym konkretnym
przypadku chodzi raczej tylko o uniknięcie ostrzeżenia ze strony
kompilatora.

Post by ***@gmail.com
A skąd mam wziąć wartość tej zmiennej? Wstawiam do równania uint64_t,
((uint64_t)(x ^ (x >> 64)
to wcale nie jest mnożenie, tylko chodzi o coś innego? Ja tu widzę
pomnóż liczbę uint64_t razy (x ^ (x >> 64).

Tak jak wyżej - uint64_t to nie jest zmienna, tylko cast. Tj.
informacja "wynik działania x xor (x shr 64) ogranicz do 64
bitów". Operacja którą podałeś wykonuje XOR na dwóch połówkach
128-bitowej wartości, wynik zapisuje w niższej połówce, a wyższą
połówkę usuwa (właśnie za pomocą castowania do uint64_t).

Mateusz