Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #34268 > unrolled thread

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

Back to article view | Back to pl.comp.programming

Contents

  Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania. "osobli...@gmail.com" <osobliwy.nick@gmail.com> - 2021-01-02 05:28 -0800
    Re: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania. Mateusz Viste <mateusz@xyz.invalid> - 2021-01-02 14:45 +0100
      Re: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania. "osobli...@gmail.com" <osobliwy.nick@gmail.com> - 2021-01-02 06:33 -0800
        Re: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania. "osobli...@gmail.com" <osobliwy.nick@gmail.com> - 2021-01-02 06:41 -0800
          Re: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania. Mateusz Viste <mateusz@xyz.invalid> - 2021-01-02 15:49 +0100
            Re: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania. "osobli...@gmail.com" <osobliwy.nick@gmail.com> - 2021-01-02 07:25 -0800
              Re: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania. Mateusz Viste <mateusz@xyz.invalid> - 2021-01-02 17:15 +0100
                Re: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania. "osobli...@gmail.com" <osobliwy.nick@gmail.com> - 2021-01-02 08:50 -0800
        Re: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania. Mateusz Viste <mateusz@xyz.invalid> - 2021-01-02 15:45 +0100

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

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.

[toc] | [next] | [standalone]

#34269

2021-01-02 o 05:28 -0800, osobli...@gmail.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

[toc] | [prev] | [next] | [standalone]

#34270

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

[toc] | [prev] | [next] | [standalone]

#34271

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

[toc] | [prev] | [next] | [standalone]

#34273

2021-01-02 o 06:41 -0800, osobli...@gmail.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

[toc] | [prev] | [next] | [standalone]

#34274

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.

[toc] | [prev] | [next] | [standalone]

#34275

2021-01-02 o 07:25 -0800, osobli...@gmail.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

[toc] | [prev] | [next] | [standalone]

#34276

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.

[toc] | [prev] | [next] | [standalone]

#34272

2021-01-02 o 06:33 -0800, osobli...@gmail.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

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web