eGospodarka.pl

eGospodarka.plGrupypl.comp.programming › Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania.
Ilość wypowiedzi w tym wątku: 9

  • 1. Data: 2021-01-02 14:28:17
    Temat: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania.
    Od: "o...@g...com" <o...@g...com>

    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.


  • 2. Data: 2021-01-02 14:45:07
    Temat: Re: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania.
    Od: Mateusz Viste <m...@x...invalid>

    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


  • 3. Data: 2021-01-02 15:33:51
    Temat: Re: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania.
    Od: "o...@g...com" <o...@g...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?

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


  • 4. Data: 2021-01-02 15:41:30
    Temat: Re: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania.
    Od: "o...@g...com" <o...@g...com>

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


  • 5. Data: 2021-01-02 15:45:55
    Temat: Re: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania.
    Od: Mateusz Viste <m...@x...invalid>

    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


  • 6. Data: 2021-01-02 15:49:22
    Temat: Re: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania.
    Od: Mateusz Viste <m...@x...invalid>

    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


  • 7. Data: 2021-01-02 16:25:26
    Temat: Re: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania.
    Od: "o...@g...com" <o...@g...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. 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.


  • 8. Data: 2021-01-02 17:15:07
    Temat: Re: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania.
    Od: Mateusz Viste <m...@x...invalid>

    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


  • 9. Data: 2021-01-02 17:50:34
    Temat: Re: Co robi permuted congruential generator XSL-RR-RR? Próbuję zrozumieć scheamt działania.
    Od: "o...@g...com" <o...@g...com>

    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.

strony : [ 1 ]



Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: