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

Groups > pl.comp.programming > #34275

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

Show all headers | View raw

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

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

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

csiph-web