Xoroshiro128 + - Xoroshiro128+

xoroshiro128 + (pojmenovaný podle jeho operací: XOR, rotace, posunutí, rotace) je a generátor pseudonáhodných čísel zamýšlen jako nástupce xorshift +. Namísto zachování tradice Marsaglie xorshift jako základní operace, xoroshiro128 + používá lineární transformaci založenou na posunu / otáčení navrženou uživatelem Sebastiano Vigna ve spolupráci s Davidem Blackmanem. Výsledkem je výrazné zlepšení rychlosti a výrazné zlepšení statistické kvality.[1]

Statistická kvalita

Nejnižší bity výstupu generovaného xoroshiro128 + mají nízkou kvalitu. Autoři xoroshiro128 + berte na vědomí, že nesplňuje všechny statistické testy s uvedením

Toto je xoroshiro128 + 1.0, náš nejlepší a nejrychlejší generátor malého stavu pro čísla s plovoucí desetinnou čárkou. Navrhujeme použít jeho horní bity pro generování s plovoucí desetinnou čárkou, protože je o něco rychlejší než xoroshiro128 **. Prochází všemi testy, o kterých víme, s výjimkou čtyř spodních bitů, které by mohly selhat v testech linearity (a jen v těch), takže pokud není nízká lineární složitost považována za problém (jak to obvykle bývá), lze ji použít ke generování 64bitové výstupy; navíc tento generátor má velmi mírnou závislost Hammingovy hmotnosti, která činí náš test (http://prng.di.unimi.it/hwd.php ) selhat po 5 TB výstupu; věříme, že toto mírné zkreslení nemůže ovlivnit žádnou aplikaci. Pokud máte obavy, použijte xoroshiro128 ** nebo xoshiro256 +.

Navrhujeme použít test znaménka k extrakci náhodné logické hodnoty a posuny doprava k extrakci podmnožin bitů.

Stát musí být nasazen, aby nebyl všude nula. Pokud máte 64bitové semeno, doporučujeme nasadit generátor splitmix64 a použít jeho výstup k vyplnění s.

POZNÁMKA: parametry (a = 24, b = 16, b = 37) této verze dávají mírně

lepší výsledky v našem testu než verze 2016 (a = 55, b = 14, c = 36).[2]

Tato tvrzení o neprocházení testů lze potvrdit spuštěním PractRand na vstupu, což má za následek výstup podobný tomuto:

RNG_test pomocí PractRand verze 0.93RNG = RNG_stdin64, seed = 0xfac83126test set = normal, folding = standard (64 bit) rng = RNG_stdin64, seed = 0xfac83126length = 128 megabajtů (2 ^ 27 bytů), čas = 2,1 sekundy Název testu Raw Zpracováno Hodnocení [ Low1 / 64] BRank (12): 256 (2) R = +3748 p ~ = 3e-1129 FAIL !!!!!!!! [Low1 / 64] BRank (12): 384 (1) R = +5405 p ~ = 3e-1628 FAIL !!!!!!!! ... a 146 výsledků bez anomálií

Autoři uznávají slabý bit nízkého řádu a dále říkají:

K extrakci náhodné logické hodnoty doporučujeme použít test znaménka[2]

Programátoři by tedy měli upřednostňovat nejvyšší bity (např. Vytváření hlav / ocasů psaním random_number <0 spíše než random_number & 1). Je však třeba poznamenat, že stejný test selhal v některých případech Mersenne Twister a STUDNA.

Jak je uvedeno v komentářích, generátor prošel testem závislosti na Hammingově váze, který vyvinuli Blackman a Vigna[3] po 5 TB dat. Pro srovnání, pro některé volby parametrů Mersenne Twister na 607 bitech selže stejný test po méně než gigabajtu dat.

Citace

David Meister, který jej implementoval v Clojure, učinil několik cenných prohlášení:

„Toto je implementace clojure xoroshiro128 + PRNG popsaná na http://xoroshiro.di.unimi.it. Ukázalo se, že algoritmus je rychlý a poskytuje vynikající statistické výsledky mnoha PRNG dodávaným s jazyky, včetně Javy. Statistické výsledky byly ověřeny autory v PractRand i TestU01. xoroshiro128 + je navržen jako nástupce xorshift128 +, který se v současné době používá v motorech JavaScript prohlížečů Chrome, Firefox a Safari. Jak xorshift128 +, tak xoroshiro128 + mají období 2128 ale xoroshiro128 + je autory srovnáván jako o 20% rychlejší as 20% méně poruchami v BigCrush než jeho předchůdce. “[4]

Matt Gallagher ve své studii generátorů náhodných čísel ve Swiftu učinil následující závěr:

Vypadá to, že Xoroshiro je nejlepší algoritmus pro obecné účely, který je v současné době k dispozici. Nízká paměť (pouze 128 bitů úložiště), extrémně vysoký výkon (1,2 nanosekundy na 64bitové číslo, po odečtení režijních nákladů na základní linii) a velmi dobře distribuované (překonání jiných algoritmů v řadě automatizovaných testů). Mersenne Twister může být stále lepší volbou pro vysoce konzervativní projekty, které nechtějí přejít na takový nový algoritmus, ale současná generace statisticky testovaných algoritmů přináší od samého počátku základní jistotu, že předchozí generace chyběly.[5]

Související generátory

  • xoroshiro128 ** zabraňuje lineárním artefaktům v nízkých bitech
  • xoshiro256 + má 256 bitů stavu, což umožňuje větší paralelismus
  • xoshiro256 ** - "náš všestranný generátor odolný vůči skále"

Generátory končící + mají slabé nízké bity, proto se doporučují pro generování čísel s plovoucí desetinnou čárkou, přičemž se používá pouze 53 nejvýznamnějších bitů.

Viz také

Reference

  1. ^ Blackman, David; Vigna, Sebastiano. "Zakódované lineární pseudonáhodné generátory". arXiv:1805.01407 [cs.DS ].
  2. ^ A b Blackman, David; Vigna, Sebastiano (2018). "Původní implementace zdrojového kódu C pro xoroshiro128 +". Citováno 4. května 2018.
  3. ^ „Testování závislostí Hammingovy váhy“. 3. května 2018. Citováno 3. května 2018.
  4. ^ Meister, David (1. srpna 2016). „Clojure implementace xoroshiro128 + PRNG popsaná na webu xoroshiro.di.unimi.it“. github.com. Citováno 2. listopadu 2016.
  5. ^ Gallagher, Matt (19. května 2016). "Generátory náhodných čísel ve Swiftu". www.cocoawithlove.com. Citováno 2. listopadu 2016.

externí odkazy