Xorshift
Xorshift slumptalsgeneratorer, även kallade skiftregistergeneratorer , är en klass av pseudoslumptalsgeneratorer som uppfanns av George Marsaglia . De är en delmängd av linjär-feedback-skiftregister (LFSR) som tillåter en särskilt effektiv implementering i mjukvara utan överdriven användning av glesa polynom . De genererar nästa nummer i sin sekvens genom att upprepade gånger ta det exklusiva eller ett nummer med en bitförskjuten version av sig själv. Detta gör exekvering extremt effektiv på modern datorarkitektur, men det gynnar inte effektiviteten i en hårdvaruimplementering. Liksom alla LFSR:er måste parametrarna väljas mycket noggrant för att uppnå en lång period.
För exekvering i programvara är xorshift-generatorer bland de snabbaste icke- kryptografiskt säkra slumptalsgeneratorerna, som kräver mycket liten kod och tillstånd. De klarar dock inte varje statistiskt test utan ytterligare förfining. Denna svaghet ändras genom att de kombineras med en icke-linjär funktion, som beskrivs i den ursprungliga artikeln. Eftersom vanliga xorshift-generatorer (utan ett icke-linjärt steg) misslyckas med vissa statistiska test, har de anklagats för att vara opålitliga.
Exempel implementering
En C- version av tre xorshift-algoritmer ges här. Den första har ett 32-bitars tillståndsord och period 2 32 −1. Den andra har ett 64-bitars tillståndsord och period 2 64 −1. Den sista har fyra 32-bitars tillståndsord och period 2 128 −1. 128-bitars algoritmen klarar de hårda testerna . Den klarar dock inte MatrixRank- och LinearComp -testerna i BigCrush- testsviten från TestU01 -ramverket.
Alla använder tre skift och tre eller fyra exklusiva-eller-operationer:
0
0
#include <stdint.h> struct xorshift32_state { uint32_t a ; }; /* Tillståndet måste initieras till icke-noll */ uint32_t xorshift32 ( struct xorshift32_state * state ) { /* Algoritmen "xor" från sid. 4 av Marsaglia, "Xorshift RNGs" */ uint32_t x = state -> a ; x ^= x << 13 ; x ^= x >> 17 ; x ^= x << 5 ; returnera tillstånd -> a = x ; } struct xorshift64_state { uint64_t a ; }; uint64_t xorshift64 ( struct xorshift64_state * state ) { uint64_t x = state -> a ; x ^= x << 13 ; x ^= x >> 7 ; x ^= x << 17 ; returnera tillstånd -> a = x ; } /* struct xorshift128_state kan alternativt definieras som ett par av uint64_t eller en uint128_t där det stöds */ struct xorshift128_state { uint32_t x [ 4 ]; }; /* Tillståndet måste initieras till icke-noll */ uint32_t xorshift128 ( struct xorshift128_state * state ) { /* Algoritmen "xor128" från sid. 5 av Marsaglia, "Xorshift RNGs" */ uint32_t t = state -> x [ 3 ]; uint32_t s = tillstånd -> x [ ]; /* Utför ett konstruerat 32-bitarsskifte. */ tillstånd -> x [ 3 ] = tillstånd -> x [ 2 ]; tillstånd -> x [ 2 ] = tillstånd -> x [ 1 ]; tillstånd -> x [ 1 ] = s ; t ^= t << 11 ; t ^= t >> 8 ; returtillstånd -> x [ ] = t ^ s ^ ( s >> 19 ) ; }
Icke-linjära variationer
Alla xorshift-generatorer misslyckas med vissa tester i BigCrush- testsviten. Detta gäller för alla generatorer baserade på linjära upprepningar, såsom Mersenne Twister eller WELL . Det är dock lätt att förvränga produktionen från sådana generatorer för att förbättra deras kvalitet.
Förvrängarna som kallas + och * lämnar fortfarande svaghet i de låga bitarna, så de är avsedda för flyttalsanvändning, eftersom konvertering till flyttal kasserar de låga bitarna. För allmänt bruk får scramblern ** (uttalas starstar ) LFSR-generatorerna att passera i alla bitar.
xorwow
Marsaglia föreslog att förvränga utgången genom att kombinera den med en enkel additiv räknare modulo 2 32 (som han kallar en "Weyl-sekvens" efter Weyls ekvifördelningssats ). Detta ökar också perioden med en faktor 2 32 till 2 192 −2 32 :
0
0
#include <stdint.h> struct xorwow_state { uint32_t x [ 5 ]; uint32_t räknare ; }; /* Tillståndsmatrisen måste initieras för att inte bara vara noll i de första fyra orden */ uint32_t xorwow ( struct xorwow_state * state ) { /* Algoritmen "xorwow" från sid. 5 av Marsaglia, "Xorshift RNGs" */ uint32_t t = state -> x [ 4 ]; uint32_t s = tillstånd -> x [ ]; /* Utför ett konstruerat 32-bitarsskifte. */ tillstånd -> x [ 4 ] = tillstånd -> x [ 3 ]; tillstånd -> x [ 3 ] = tillstånd -> x [ 2 ]; tillstånd -> x [ 2 ] = tillstånd -> x [ 1 ]; tillstånd -> x [ 1 ] = s ; t ^= t >> 2 ; t ^= t << 1 ; t ^= s ^ ( s << 4 ); tillstånd -> x [ ] = t ; tillstånd -> räknare += 362437 ; returnera t + tillstånd -> räknare ; }
Detta fungerar bra, men misslyckas med några tester i BigCrush. Denna generator är standard i Nvidias CUDA -verktygssats.
xorshift*
En xorshift* -generator tillämpar en inverterbar multiplikation (modulo ordstorleken) som en icke-linjär transformation till utsignalen från en xorshift -generator, som föreslagits av Marsaglia. Alla xorshift* -generatorer sänder ut en sekvens av värden som är jämnt fördelade i maximalt möjliga dimension (förutom att de aldrig kommer att mata ut noll för 16 anrop, dvs. 128 byte, i rad).
Följande 64-bitars generator har en maximal period på 2 64 −1.
#include <stdint.h> /* xorshift64s, variant A_1(12,25,27) med multiplikator M_32 från rad 3 i tabell 5 */ uint64_t xorshift64star ( void ) { static uint64_t x = 1 ; /* initialt seed måste vara icke-noll, använd inte en statisk variabel för tillståndet om det är flertrådigt */ x ^= x >> 12 ; x ^= x << 25 ; x ^= x >> 27 ; returnera x * 0x2545F4914F6CDD1DULL ; }
Generatorn misslyckas endast i MatrixRank -testet av BigCrush, men om generatorn modifieras för att endast returnera de höga 32 bitarna, så klarar den BigCrush med noll fel. Faktum är att en reducerad version med endast 40 bitars internt tillstånd passerar sviten, vilket tyder på en stor säkerhetsmarginal. En liknande generator som föreslås i Numerical Recipes som RanQ1 klarar inte heller BirthdaySpacings- testet.
Vigna föreslår följande xorshift1024* -generator med 1024 bitar av tillstånd och en maximal period på 2 1024 −1; men det går inte alltid igenom BigCrush. xoshiro256** är därför ett mycket bättre alternativ.
#include <stdint.h> /* Tillståndet måste seedas så att det finns minst ett element som inte är noll i arrayen */ struct xorshift1024s_state { uint64_t x [ 16 ]; int index ; }; uint64_t xorshift1024s ( struct xorshift1024s_state * state ) { int index = state -> index ; uint64_t const s = state -> x [ index ++ ]; uint64_t t = tillstånd -> x [ index &= 15 ]; t ^= t << 31 ; // a t ^= t >> 11 ; // b -- Återigen, skiftningarna och multiplikatorerna är avstämbara t ^= s ^ ( s >> 30 ); // c state -> x [ index ] = t ; state -> index = index ; returnera t * 1181783497276652981ULL ; }
xorshift+
En xorshift+ -generator kan uppnå en storleksordning färre fel än Mersenne Twister eller WELL . En inbyggd C-implementering av en xorshift+-generator som klarar alla tester från BigCrush-sviten kan vanligtvis generera ett slumpmässigt tal på färre än 10 klockcykler på x86 , tack vare instruktionspipelining .
Istället för att använda multiplikation är det möjligt att använda addition som en snabbare icke-linjär transformation. Idén föreslogs först av Saito och Matsumoto (också ansvariga för Mersenne Twister) i XSadd -generatorn, som lägger till två på varandra följande utgångar från en underliggande xorshift -generator baserad på 32-bitars skift. En nackdel med att lägga till på varandra följande utgångar är dock att medan den underliggande xorshift128- generatorn är 2-dimensionellt likafördelad, är xorshift128+ -generatorn endast endimensionellt likafördelad.
XSadd har en viss svaghet i de lågordnade bitarna i dess utdata; den misslyckas med flera BigCrush-tester när utdataorden är bitomvända. För att rätta till detta problem introducerade Vigna xorshift+ , baserad på 64-bitarsskift. xorshift+ -generatorer, även så stora som xorshift1024+ , uppvisar viss detekterbar linjäritet i lågordningens bitar av deras utdata; den passerar BigCrush, men gör det inte när de 32 bitarna av lägsta ordningen används i omvänd ordning från varje 64-bitars ord. Denna generator är en av de snabbaste generatorerna som passerar BigCrush.
Följande xorshift128+ -generator använder 128 bitars tillstånd och har en maximal period på 2 128 −1.
0
0
#include <stdint.h> struct xorshift128p_state { uint64_t x [ 2 ]; }; /* Tillståndet måste seedas så att det inte är noll */ uint64_t xorshift128p ( struct xorshift128p_state * state ) { uint64_t t = state -> x [ ]; uint64_t const s = state -> x [ 1 ]; tillstånd -> x [ ] = s ; t ^= t << 23 ; // a t ^= t >> 18 ; // b -- Återigen, skiftningarna och multiplikatorerna är avstämbara t ^= s ^ ( s >> 5 ); // c state -> x [ 1 ] = t ; returnera t + s ; }
xoshiro
xoshiro och xoroshiro använder rotationer utöver skift. Enligt Vigna är de snabbare och producerar bättre kvalitet än xorshift.
Denna klass av generator har varianter för 32-bitars och 64-bitars heltal och flyttalsutmatning; för flyttals tar man de övre 53 bitarna (för binary64 ) eller de övre 23 bitarna (för binary32 ), eftersom de övre bitarna är av bättre kvalitet än de lägre bitarna i flyttalsgeneratorerna. Algoritmerna inkluderar också en hoppfunktion , som sätter tillståndet framåt med ett visst antal steg – vanligtvis en tvåpotens som gör att många exekveringstrådar kan starta vid distinkta initiala tillstånd.
För 32-bitars utdata är xoshiro128** och xoshiro128+ exakt ekvivalenta med xoshiro256** och xoshiro256+, med uint32_t istället för uint64_t och med olika skift-/rotationskonstanter.
På senare tid har xoshiro++- generatorerna gjorts som ett alternativ till xoshiro**- generatorerna. De används i vissa implementeringar av Fortran- kompilatorer som GNU Fortran, Java och Julia .
xoshiro256**
xoshiro256** är familjens allmänna slumpmässiga 64-bitars nummergenerator. Det används i Lua och .NET Framework .
0
0
/* Anpassad från koden som finns på Sebastiano Vignas hemsida */ #include <stdint.h> uint64_t rol64 ( uint64_t x , int k ) { return ( x << k ) | ( x >> ( 64 - k )); } struct xoshiro256ss_state { uint64_t s [ 4 ]; }; uint64_t xoshiro256ss ( struct xoshiro256ss_state * state ) { uint64_t * s = state -> s ; uint64_t const resultat = rol64 ( s [ 1 ] * 5 , 7 ) * 9 ; uint64_t const t = s [ 1 ] << 17 ; s [ 2 ] ^= s [ ]; s [ 3 ] ^= s [ 1 ]; s [ 1 ] ^= s [ 2 ]; s [ ] ^= s [ 3 ]; s [ 2 ] ^= t ; s [ 3 ] = rol64 ( s [ 3 ], 45 ); returnera resultat ; }
xoshiro256+
xoshiro256+ är ungefär 15 % snabbare än xoshiro256**, men de lägsta tre bitarna har låg linjär komplexitet; därför bör den endast användas för flyttalsresultat genom att extrahera de övre 53 bitarna.
0
0
0
#include <stdint.h> uint64_t rol64 ( uint64_t x , int k ) { return ( x << k ) | ( x >> ( 64 - k )); } struct xoshiro256p_state { uint64_t s [ 4 ]; }; uint64_t xoshiro256p ( struct xoshiro256p_state * state ) { uint64_t * s = state -> s ; uint64_t const result = s [ ] + s [ 3 ]; uint64_t const t = s [ 1 ] << 17 ; s [ 2 ] ^= s [ ]; s [ 3 ] ^= s [ 1 ]; s [ 1 ] ^= s [ 2 ]; s [ ] ^= s [ 3 ]; s [ 2 ] ^= t ; s [ 3 ] = rol64 ( s [ 3 ], 45 ); returnera resultat ; }
xoroshiro
Om utrymmet är högst, motsvarar xoroshiro128** och xoroshiro128+ xoshiro256** och xoshiro256+. Dessa har mindre tillståndsutrymmen och är därför mindre användbara för massivt parallella program. xoroshiro128+ uppvisar också ett milt beroende i befolkningsantalet , vilket genererar ett fel efter 5 TB utgång. Författarna tror inte att detta kan upptäckas i verkliga program.
xoroshiro64** och xoroshiro64* är ekvivalenta med xoroshiro128** och xoroshiro128+. Till skillnad från xoshiro-generatorerna är de inte enkla portar för sina motsvarigheter med högre precision.
Initialisering
I xoshiro-papperet rekommenderas det att initiera tillståndet för generatorerna med en generator som är radikalt skild från de initierade generatorerna, samt en som aldrig kommer att ge "helt noll"-tillståndet; för skiftregistergeneratorer är detta tillstånd omöjligt att komma ifrån. Författarna rekommenderar specifikt att du använder SplitMix64-generatorn, från ett 64-bitars frö, enligt följande:
0
#include <stdint.h> struct splitmix64_state { uint64_t s ; }; uint64_t splitmix64 ( struct splitmix64_state * state ) { uint64_t result = ( state -> s += 0x9E3779B97f4A7C15 ); resultat = ( resultat ^ ( resultat >> 30 )) * 0xBF58476D1CE4E5B9 ; resultat = ( resultat ^ ( resultat >> 27 )) * 0x94D049BB133111EB ; returnera resultat ^ ( resultat >> 31 ); } struct xorshift128_state { uint32_t x [ 4 ]; }; // man skulle kunna göra samma sak för vilken som helst av de andra generatorerna void xorshift128_init ( struct xorshift128_state * state , uint64_t seed ) { struct splitmix64_state smstate = { seed }; uint64_t tmp = splitmix64 ( & smstate ); state -> x [ ] = ( uint32_t ) tmp ; state -> x [ 1 ] = ( uint32_t )( tmp >> 32 ); tmp = splitmix64 ( & smstate ); state -> x [ 2 ] = ( uint32_t ) tmp ; state -> x [ 3 ] = ( uint32_t )( tmp >> 32 ); }
Anteckningar
Vidare läsning
- Brent, Richard P. (juli 2006). "Vissa långvariga slumptalsgeneratorer som använder skift och xor" . ANZIAM Journal . 48 : C188–C202. Listar generatorer av olika storlekar med fyra skift (två per återkopplingsord).