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.

do góry

2021-01-02 o 05:28 -0800, o...@g...com napisał:
> 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.

> 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.

> Co to jest uint64_t?

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

> 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.

> 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

do góry

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?

> 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.

> > 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).

do góry

> 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?

do góry

2021-01-02 o 06:33 -0800, o...@g...com napisał:
> 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.

> 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).

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

do góry

2021-01-02 o 06:41 -0800, o...@g...com napisał:
> > 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.

> Rozumiem, że większą niż 64 bity?

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

> 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

do góry

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.

do góry

2021-01-02 o 07:25 -0800, o...@g...com napisał:
> 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".

> 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.

> 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.

> 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.

> 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ę.

> >> 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.

> 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

do góry

Znalazłem coś takiego na stronie autora:

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

#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.

do góry