Lista över slumptalsgeneratorer

Slumptalsgeneratorer är viktiga i många typer av tekniska tillämpningar, inklusive fysik , teknik eller matematiska datorstudier (t.ex. Monte Carlo -simuleringar), kryptografi och spel (på spelservrar ).

Den här listan innehåller många vanliga typer, oavsett kvalitet eller tillämplighet för ett givet användningsfall.

Pseudoslumptalsgeneratorer (PRNG)

När du använder en pseudoslumptalsgenerator , tänk på John von Neumanns påstående "Alla som överväger aritmetiska metoder för att producera slumpmässiga siffror är, naturligtvis, i ett tillstånd av synd."

Följande algoritmer är pseudoslumptalsgeneratorer.

Generator Datum Första förespråkarna Referenser Anteckningar
Mellankvadratmetod 1946 J. von Neumann I sin ursprungliga form är den av dålig kvalitet och endast av historiskt intresse.
Lehmer generator 1951 DH Lehmer En av de allra tidigaste och mest inflytelserika designerna.
Linjär kongruentialgenerator (LCG) 1958 VI Thomson; A. Rotenberg En generalisering av Lehmer-generatorn och historiskt sett den mest inflytelserika och studerade generatorn.
Lagged Fibonacci-generator (LFG) 1958 GJ Mitchell och DP Moore
Linjär-feedback-skiftregister (LFSR) 1965 RC Tausworthe En enormt inflytelserik design. Kallas även Tausworthe-generatorer.
Wichmann–Hill generator 1982 BA Wichmann och DI Hill En kombination av tre små LCG:er, lämpade för 16-bitars CPU:er . Används flitigt i många program, t.ex. används det i Excel 2003 och senare versioner för Excel-funktionen RAND och det var standardgeneratorn i språket Python upp till version 2.2.
Regel 30 1983 S. Wolfram Baserat på cellulära automater.
Inversiv kongruentialgenerator (ICG) 1986 J. Eichenauer och J. Lehn
Blum Blum Shub 1986 M. Blum, L. Blum och M. Shub Blum-Blum-Shub är en PRNG-algoritm som anses vara kryptografiskt säker. Dess bas är baserad på primtal.
Park-Miller generator 1988 SK Park och KW Miller En specifik implementering av en Lehmer-generator, flitigt använd eftersom den ingår i C++ som funktionen minstd_rand0 från C++11 och framåt.
ACORN generator (upptäckt 1984) 1989 RS Wikramaratna Generatorn för tilläggskongruentiella R andomnummer . _ _ _

Enkel att implementera, snabb, men inte allmänt känd. Med lämpliga initieringar, klarar alla aktuella empiriska testsviter och har formellt visat sig konvergera. Lätt att förlänga för godtycklig periodlängd och förbättrad statistisk prestanda över högre dimensioner och med högre precision.
MIXMAX generator 1991 GK Savvidy och NG Ter-Arutyunyan-Savvidy Det är en medlem av klassen av linjär kongruential matrisgenerator, en generalisering av LCG. Grunden bakom MIXMAX-familjen av generatorer bygger på resultat från ergodisk teori och klassisk mekanik.
Add-with-carry (AWC) 1991 G. Marsaglia och A. Zaman En modifiering av Lagged-Fibonacci-generatorer.
Subtrahera-med-låna (SWB) 1991 G. Marsaglia och A. Zaman En modifiering av Lagged-Fibonacci-generatorer. En SWB-generator är grunden för RANLUX-generatorn, flitigt använd för t.ex. partikelfysiksimuleringar.
Maximalt periodiska ömsesidiga 1992 RAJ Matthews En metod med rötter i talteorin, men aldrig använd i praktiska tillämpningar.
KYSS 1993 G. Marsaglia Prototypiskt exempel på en kombinationsgenerator.
Multiplicera-med-bära (MWC) 1994 G. Marsaglia; C. Koç
Complementary-multiply-with-carry (CMWC) 1997 R. Couture och P. L'Ecuyer
Mersenne Twister (MT) 1998 M. Matsumoto och T. Nishimura Nära besläktad med LFSRs. I sin MT19937-implementering är förmodligen den mest använda moderna PRNG. Standardgenerator i R och Python-språket från och med version 2.3.
Xorshift 2003 G. Marsaglia Det är en mycket snabb undertyp av LFSR-generatorer. Marsaglia föreslog också som en förbättring xorwow-generatorn, där utsignalen från en xorshift-generator läggs till med en Weyl-sekvens . xorwow-generatorn är standardgeneratorn i CURAND-biblioteket i nVidia CUDA- applikationsprogrammeringsgränssnittet för grafikbehandlingsenheter.
Väl jämnt fördelad långperiodisk linjär (WELL) 2006 F. Panneton, P. L'Ecuyer och M. Matsumoto En LFSR nära besläktad med Mersenne Twister, som syftar till att åtgärda några av dess brister.
En liten icke-kryptografisk PRNG (JSF) 2007 Bob Jenkins
Advanced Randomization System (ARS) 2011 J. Salmon, M. Moraes, R. Dror och D. Shaw En förenklad version av AES-blockchifferet , vilket leder till mycket snabb prestanda på system som stöder AES-NI .
Threefry 2011 J. Salmon, M. Moraes, R. Dror och D. Shaw En förenklad version av Threefish-blockchifferet, lämplig för GPU-implementeringar.
Philox 2011 J. Salmon, M. Moraes, R. Dror och D. Shaw En förenkling och modifiering av blockchifferet Threefish med tillägg av en S-box .
WELLDOC 2013 L. Balkova, M. Bucci, A. de Luca, J. Hladky, S. Puzynina Aperiodiska pseudoslumptalsgeneratorer baserade på teknik för oändliga ord.
SplitMix 2014 GL Steele, D. Lea och CH Flood Baserat på den slutliga blandningsfunktionen i MurmurHash3. Ingår i Java Development Kit 8 och högre.
Permuted Congruential Generator (PCG) 2014 JAG O'Neill En modifiering av LCG.
Random Cycle Bit Generator (RCB) 2016 R. Cookman RCB beskrivs som en bitmönstergenerator gjord för att övervinna några av bristerna med Mersenne Twister och korta perioder/bitlängdsbegränsningar hos shift/modulo-generatorer.
Middle-Square Weyl Sequence RNG (se även middle-square-metoden ) 2017 B. Widynski En variant på John von Neumanns ursprungliga mellankvadratmetod , denna generator kan vara den snabbaste RNG som klarar alla statistiska tester.
Xoroshiro128+ 2018 D. Blackman, S. Vigna En modifiering av Marsaglias Xorshift-generatorer, en av de snabbaste generatorerna på moderna 64-bitars processorer. Relaterade generatorer inkluderar xoroshiro128**, xoshiro256+ och xoshiro256**.
64-bitars MELG (MELG-64) 2018 S. Harase, T. Kimoto En implementering av 64-bitars maximalt likafördelade F 2 -linjära generatorer med Mersenne prime period.
Rutor RNG 2020 B. Widynski En motbaserad version av Middle-Square Weyl Sequence RNG . Liknar Philox i design men betydligt snabbare.

Kryptografiska algoritmer

Chifferalgoritmer och kryptografiska hash kan användas som pseudoslumptalsgeneratorer av mycket hög kvalitet. Men i allmänhet är de betydligt långsammare (vanligtvis med en faktor 2-10) än snabba, icke-kryptografiska slumptalsgeneratorer.

Dessa inkluderar:

Ett fåtal kryptografiskt säkra pseudoslumptalsgeneratorer förlitar sig inte på chifferalgoritmer utan försöker matematiskt koppla svårigheten att särskilja sin utdata från en "sann" slumpmässig ström till ett beräkningssvårt problem. Dessa tillvägagångssätt är teoretiskt viktiga men är för långsamma för att vara praktiska i de flesta tillämpningar. De inkluderar:

Slumptalsgeneratorer som använder extern entropi

Dessa tillvägagångssätt kombinerar en pseudoslumptalsgenerator (ofta i form av ett block- eller strömchiffer) med en extern källa till slumpmässighet (t.ex. musrörelser, fördröjning mellan tangentbordstryck etc.).

Se även

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=List_of_random_number_generators&oldid=1133527214 "