Xoroshiro128+

xoroshiro128+ (nazwany tak od swoich operacji: XOR, obracanie, przesuwanie, obracanie) to generator liczb pseudolosowych , który ma być następcą xorshift+ . Zamiast utrwalać tradycję Marsaglii polegającą na xorshift jako podstawowej operacji, xoroshiro128+ wykorzystuje liniową transformację opartą na przesunięciu/obrocie, zaprojektowaną przez Sebastiano Vignę we współpracy z Davidem Blackmanem. Rezultatem jest znaczna poprawa szybkości i jakości statystycznej.

Jakość statystyczna

Najniższe bity danych wyjściowych generowanych przez xoroshiro128+ mają niską jakość. Autorzy xoroshiro128+ przyznają, że nie przechodzi on wszystkich testów statystycznych, stwierdzając

To jest xoroshiro128+ 1.0, nasz najlepszy i najszybszy generator małych stanów dla liczb zmiennoprzecinkowych. Sugerujemy użycie jego górnych bitów do generowania liczb zmiennoprzecinkowych, ponieważ jest nieco szybszy niż xoroshiro128**. Przechodzi wszystkie znane nam testy z wyjątkiem czterech niższych bitów, które mogą nie przejść testów liniowości (i tylko tych), więc jeśli niska złożoność liniowa nie jest uważana za problem (jak to zwykle bywa), można go użyć do wygenerowania Wyjścia 64-bitowe też; co więcej, ten generator ma bardzo łagodną zależność od wagi Hamminga, dzięki czemu nasz test ( http://prng.di.unimi.it/hwd.php ) awaria po 5 TB danych wyjściowych; uważamy, że to niewielkie odchylenie nie może wpłynąć na żadną aplikację. Jeśli jesteś zaniepokojony, użyj xoroshiro128** lub xoshiro256+.

Sugerujemy użycie testu znaku w celu wyodrębnienia losowej wartości logicznej oraz przesunięć w prawo w celu wyodrębnienia podzbiorów bitów.

Stan musi być zaszczepiony tak, aby nie wszędzie wynosił zero. Jeśli masz 64-bitowy seed, sugerujemy zainicjowanie generatora splitmix64 i wykorzystanie jego danych wyjściowych do wypełnienia s.

UWAGA: parametry (a=24, b=16, c=37) tej wersji nieznacznie ustępują

lepsze wyniki w naszym teście niż wersja 2016 (a=55, b=14, c=36).

Te twierdzenia o niezdaniu testów można potwierdzić, uruchamiając PractRand na danych wejściowych, co daje wynik podobny do pokazanego poniżej:

RNG_test przy użyciu PractRand w wersji 0.93 RNG = RNG_stdin64, seed = 0xfac83126 zestaw testowy = normalny, składany = standardowy (64 bity) rng=RNG_stdin64, seed=0xfac83126 length= 128 megabajtów (2^27 bajtów), czas= 2,1 sekundy Nazwa testu Raw Processed Ocena [Niski1/64]BRank(12):256(2) R= +3748 p~= 3e-1129 NIEPOWODZENIE !!!!!!!! [Low1/64]BRank(12):384(1) R= +5405 p~= 3e-1628 NIEPOWODZENIE !!!!!!!! ...i 146 wyników badań bez anomalii

Uznając autorów, przejdź do:

Sugerujemy użycie testu znaku w celu wyodrębnienia losowej wartości logicznej

Dlatego programiści powinni preferować najwyższe bity (np. tworzenie orła/reszki przez napisanie random_number < 0 zamiast random_number & 1 ). Należy jednak zauważyć, że ten sam test kończy się niepowodzeniem w niektórych przypadkach Mersenne Twister i WELL .

Problemy statystyczne wykraczają daleko poza kilka dolnych bitów, ponieważ nie zdaje testu PractRand, nawet gdy jest obcięty, i nie przechodzi wielu testów w BigCrush, nawet gdy bity są odwrócone.

Cytaty

David Meister, który zaimplementował go w Clojure , wygłosił kilka cennych stwierdzeń:

„Jest to implementacja clojure xoroshiro128+ PRNG opisana na stronie http://xoroshiro.di.unimi.it . Wykazano, że algorytm jest szybki i daje lepsze wyniki statystyczne niż wiele PRNG dostarczanych z językami, w tym Javą. Wyniki statystyczne zostały zweryfikowane przez autorów zarówno w PractRand, jak i TestU01. xoroshiro128+ ma być następcą xorshift128+, obecnie używanego w silnikach JavaScript Chrome, Firefox i Safari. Zarówno xorshift128+, jak i xoroshiro128+ mają okres 2 128 ale xoroshiro128+ jest porównywany przez autorów jako o 20% szybszy i z 20% mniejszą liczbą awarii w BigCrush niż jego poprzednik”.

Matt Gallagher w swoim badaniu dotyczącym generatorów liczb losowych w Swift doszedł do następującego wniosku:

Wygląda na to, że Xoroshiro jest obecnie najlepszym dostępnym algorytmem ogólnego przeznaczenia. Mała pamięć (tylko 128 bitów pamięci), wyjątkowo wysoka wydajność (1,2 nanosekundy na liczbę 64-bitową, po odjęciu kosztów ogólnych) i bardzo dobra dystrybucja (pokonując inne algorytmy w szeregu zautomatyzowanych testów). Mersenne Twister może nadal być lepszym wyborem dla bardzo konserwatywnych projektów, które nie chcą przejść na taki nowy algorytm, ale obecna generacja statystycznie przetestowanych algorytmów zapewnia od samego początku podstawę pewności, której brakowało poprzednim generacjom.

Powiązane generatory

  • xoroshiro128** zapobiega liniowym artefaktom w niskich bitach
  • xoshiro256+ ma 256 bitów stanu, co pozwala na większą równoległość
  • xoshiro256** — „nasz uniwersalny, solidny generator”

Generatory kończące się na + mają słabe niskie bity, dlatego są zalecane do generowania liczb zmiennoprzecinkowych, używając tylko 53 najbardziej znaczących bitów.

Zobacz też

  1. Bibliografia _ Vigna, Sebastiano (2018). „Zakodowane liniowe generatory pseudolosowe”. arXiv : 1805.01407 [ cs.DS ].
  2. ^ a b Blackman, David; Vigna, Sebastiano (2018). „Oryginalna implementacja kodu źródłowego C xoroshiro128+” . Źródło 4 maja 2018 r .
  3. ^ „xoroshiro zawodzi PractRand po obcięciu” . 2020 . Źródło 30 grudnia 2020 r .
  4. ^ „Generator liczb losowych Xorshift128+ zawodzi BigCrush” . 2020 . Źródło 30 grudnia 2020 r .
  5. ^ Meister, David (1 sierpnia 2016). „Implementacja Clojure xoroshiro128+ PRNG opisana na stronie internetowej xoroshiro.di.unimi.it” . github.com . Źródło 2 listopada 2016 r .
  6. ^ Gallagher, Matt (19 maja 2016). „Generatory liczb losowych w Swift” . www.cocoawithlove.com . Źródło 2 listopada 2016 r .

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Xoroshiro128%2B&oldid=1128821751 ”