Seznam generátorů náhodných čísel - List of random number generators

Generátory náhodných čísel jsou důležité v mnoha druzích technických aplikací, včetně fyzika, inženýrství nebo matematický počítačové studie (např. Monte Carlo simulace), kryptografie a hazard (na herní servery ).

Tento seznam obsahuje mnoho běžných typů bez ohledu na kvalitu.

Generátory pseudonáhodných čísel (PRNG)

Kdykoli používáte a generátor pseudonáhodných čísel, mějte na paměti John von Neumann Výrok "Každý, kdo uvažuje o aritmetických metodách vytváření náhodných číslic, je samozřejmě ve stavu hříchu."[1]

Následující algoritmy jsou generátory pseudonáhodných čísel.

GenerátordatumPrvní navrhovateléReferencePoznámky
Metoda středního čtverce1946J. von Neumann[2]Ve své původní podobě je nekvalitní a má pouze historický význam.
Lehmerův generátor1951D. H. Lehmer[3]Jeden z nejranějších a nejvlivnějších návrhů.
Lineární kongruentní generátor (LCG)1958W. E. Thomson; A. Rotenberg[4][5]Zobecnění Lehmerova generátoru a historicky nejvlivnějšího a studovaného generátoru.
Zpožděný generátor Fibonacci (LFG)1958G. J. Mitchell a D. P. Moore[6]
Posuvný registr lineární zpětné vazby (LFSR)1965R. C. Tausworthe[7]Obrovský vlivný design. Také se nazývají generátory Tausworthe.
Wichmann – Hillův generátor1982B. A. Wichmann a D. I. Hill[8]Kombinace tří malých LCG vhodných pro 16bitové procesory. Široce se používá v mnoha programech, např. používá se v Vynikat 2003 a novější verze pro funkci RAND[9] a byl to výchozí generátor v jazyce Python až do verze 2.2.[10]
Pravidlo 301983S. Wolfram[11]Na základě celulárních automatů.
Inverzní shodný generátor (ICG)1986J. Eichenauer a J. Lehn[12]
Generátor Park-Miller1988S. K. Park a K. W. Miller[13]Specifická implementace Lehmerova generátoru, široce používaná, protože je zabudována do C a C ++ jazyky jako funkce `minstd '.
ACORN generátor(objeveno 1984) 1989R. S. Wikramaratna[14] [15]The Additive Spolzásadní Random Ngenerátor okolík.

Jednoduchá implementace, rychlá, ale není příliš známá. S vhodnou inicializací projde všemi současnými empirickými testovacími sadami a je formálně prokázáno, že konverguje. Snadno se prodlužuje pro libovolnou délku období a zlepšuje statistický výkon ve vyšších dimenzích as vyšší přesností.

Generátor MIXMAX1991G. K. Savvidy a N. G. Ter-Arutyunyan-Savvidy[16]Je členem třídy maticového lineárního kongruenčního generátoru, generalizace LCG. Zdůvodnění generátorů rodiny MIXMAX se opírá o výsledky ergodické teorie a klasické mechaniky.
Add-with-carry (AWC)1991G. Marsaglia a A. Zaman[17]Modifikace generátorů Lagged-Fibonacci.
Odečíst s půjčením (SWB)1991G. Marsaglia a A. Zaman[17]Modifikace generátorů Lagged-Fibonacci. Generátor SWB je základem pro generátor RANLUX,[18] široce používaný např. pro simulace částicové fyziky.
Maximálně periodické reciproční1992R. A. J. Matthews[19]Metoda s kořeny v teorii čísel, i když se nikdy nepoužívá v praktických aplikacích.
POLIBEK1993G. Marsaglia[20]Prototypický příklad kombinovaného generátoru.
Několikanásobné přenášení (MWC)1994G. Marsaglia; C. Koç[21][22]
Doplňkové násobení s přenášením (CMWC)1997R. Couture a P. L’Ecuyer[23]
Mersenne Twister (MT)1998M. Matsumoto a T. Nishimura[24]Úzce souvisí s LFSR. Ve své implementaci MT19937 je pravděpodobně nejčastěji používaným moderním PRNG. Výchozí generátor v R a Jazyk Python od verze 2.3.
Xorshift2003G. Marsaglia[25]Je to velmi rychlý podtyp generátorů LFSR. Marsaglia také navrhla jako vylepšení generátor xorwow, ve kterém je výstup generátoru xorshift přidán s Weylova sekvence. Generátor xorwow je výchozí generátor v knihovně CURAND v nVidia CUDA aplikační programovací rozhraní pro jednotky grafického zpracování.
Dobře ekvidistribuované lineární lineární období (STUDNA)2006F. Panneton, P. L'Ecuyer a M. Matsumoto[26]LFSR úzce souvisí s Mersenne Twister, jehož cílem je napravit některé z jeho nedostatků.
Malý nekryptografický PRNG (JSF)2007Bob Jenkins[27]
Pokročilý randomizační systém (ARS)2011J. Salmon, M. Moraes, R. Dror a D. Shaw[28]Zjednodušená verze Bloková šifra AES, což vede k velmi rychlému výkonu systému podporujícího AES-NI.
Threefry2011J. Salmon, M. Moraes, R. Dror a D. Shaw[28]Zjednodušená verze blokové šifry Threefish, vhodná pro implementace GPU.
Philox2011J. Salmon, M. Moraes, R. Dror a D. Shaw[28]Zjednodušení a úprava blokové šifry Threefish s přidáním S-box.
SplitMix2014G. L. Steele, D. Lea a C. H. Flood[29]Na základě konečné funkce míchání MurmurHash3. Zahrnuto v Java Development Kit 8 a novějších.
Permuted Congruential Generator (PCG)2014M. E. O'Neill[30]Modifikace LCG.
Generátor bitů náhodného cyklu (RCB)2016R. Cookman[31]RCB je popisován jako generátor bitových vzorů, který je určen k překonání některých nedostatků s Mersenne Twister a omezením krátkých období / bitové délky generátorů posunu / modulo.
Middle Square Weyl Sequence PRNG2017B. Widynski[32]Variace na John von Neumann je originál metoda středního čtverce, tento generátor může být nejrychlejším PRNG, který projde všemi statistickými testy.
Xoroshiro128 +2018D. Blackman, S. Vigna[33]Modifikace generátorů Xorshift společnosti Marsaglia, jednoho z nejrychlejších generátorů v moderní době 64-bit CPU. Mezi související generátory patří xoroshiro128 **, xoshiro256 + a xoshiro256 **.
64bitový MELG2018S. Harase, T. Kimoto[34]Implementace 64-bit maximálně ekvidistribuované F2-lineární generátory s Mersennovým prime obdobím.
Čtverce RNG2020B. Widynski[35]A založené na pultu verze Middle Square Weyl Sequence PRNG. Podle autora se to jeví jako jedno z nejrychlejších založené na pultu generátory.

Kryptografické algoritmy

Šifra algoritmy a kryptografické hashe lze použít jako velmi kvalitní generátory pseudonáhodných čísel. Obecně jsou však podstatně pomalejší (obvykle o faktor 2–10) než rychlé generátory náhodných čísel bez kryptografie.

Tyto zahrnují:

Několik kryptograficky bezpečných generátorů pseudonáhodných čísel se nespoléhá na šifrovací algoritmy, ale snaží se matematicky spojit obtížnost rozlišení jejich výstupu od `` skutečného`` náhodného proudu s výpočetně obtížným problémem. Tyto přístupy jsou teoreticky důležité, ale jsou příliš pomalé na to, aby byly praktické ve většině aplikací. Obsahují:

Generátory náhodných čísel, které používají externí entropii

Tyto přístupy kombinují generátor pseudonáhodných čísel (často ve formě blokové nebo proudové šifry) s externím zdrojem náhodnosti (např. Pohyby myší, zpoždění mezi stiskem klávesnice atd.).

Servery s náhodným číslem

Následující (neúplný) seznam webů tvrdí, že poskytuje náhodná čísla generovaná ze skutečně náhodného zdroje, přičemž mnoho z nich poskytuje další služby randomizace:

Známá rozhraní API PRNG

Viz také

Reference

  1. ^ Von Neumann, John (1951). "Různé techniky používané v souvislosti s náhodnými číslicemi" (PDF). Série Národního úřadu pro aplikovanou matematiku. 12: 36–38.
  2. ^ Některé von Neumannovy dokumenty z roku 1949 byly vytištěny až v roce 1951. John von Neumann, „Různé techniky používané v souvislosti s náhodnými číslicemi“, v A.S. Householder, G.E. Forsythe a H.H. Germond, eds., Metoda Monte Carlo, National Bureau of Standards Applied Mathematics Series, sv. 12 (Washington, D.C .: U.S. Government Printing Office, 1951): str. 36-38.
  3. ^ Lehmer, Derrick H. (1951). "Matematické metody ve velkých výpočetních jednotkách". Sborník z 2. sympozia o digitálních počítacích strojích velkého rozsahu: 141–146.
  4. ^ Thomson, W. E. (1958). „Modifikovaná metoda kongruence generování pseudonáhodných čísel“. Počítačový deník. 1 (2): 83. doi:10.1093 / comjnl / 1.2.83.
  5. ^ Rotenberg, A. (1960). "Nový generátor pseudonáhodných čísel". Deník ACM. 7 (1): 75–77. doi:10.1145/321008.321019.
  6. ^ D. E. Knuth, The Art of Computer Programming, sv. 2 Seminumerical Algorithms, 3. vyd., Addison Wesley Longman (1998); Viz str. 27.
  7. ^ Tausworthe, R. C. (1965). "Náhodná čísla generovaná lineárním opakováním Modulo Two" (PDF). Matematika výpočtu. 19 (90): 201–209. doi:10.1090 / S0025-5718-1965-0184406-1.
  8. ^ Wichmann, Brian A .; Hill, David I. (1982). "Algoritmus AS 183: Efektivní a přenosný generátor pseudonáhodných čísel". Journal of the Royal Statistical Society. Series C (Applied Statistics). 31 (2): 188–190. doi:10.2307/2347988. JSTOR  2347988.
  9. ^ „Podpora Microsoftu - Popis funkce RAND v aplikaci Excel“. 17. dubna 2018.
  10. ^ "Dokumentace» Standardní knihovna Pythonu »9. Numerické a matematické moduly» 9.6. Random - Generování pseudonáhodných čísel ".
  11. ^ Wolfram, S. (1983). "Statistická mechanika celulárních automatů". Rev. Mod. Phys. 55 (3): 601–644. Bibcode:1983RvMP ... 55..601W. doi:10.1103 / RevModPhys.55,601.
  12. ^ Eichenauer, Jürgen; Lehn, Jürgen (1986). Msgstr "Nelineární shodný generátor pseudonáhodných čísel". Statistische Hefte. 27: 315–326. doi:10.1007 / BF02932576.
  13. ^ Park, Stephen K .; Miller, Keith W. (1988). „Generátory náhodných čísel: Dobré je těžké najít“ (PDF). Komunikace ACM. 31 (10): 1192–1201. doi:10.1145/63039.63042.
  14. ^ Wikramaratna, R. S. (1989). "ACORN - nová metoda pro generování sekvencí rovnoměrně rozložených pseudonáhodných čísel". Journal of Computational Physics. 83 (1): 16–31. Bibcode:1989JCoPh..83 ... 16W. doi:10.1016/0021-9991(89)90221-0.
  15. ^ Wikramaratna, R.S. Výsledky teoretické a empirické konvergence pro aditivní generátory shodných náhodných čísel, Journal of Computational and Applied Mathematics (2009), doi: 10,1016 / j.cam.2009.10.015
  16. ^ Savvidy, G. K.; Ter-Arutyunyan-Savvidy, N.G ​​(1991). "Na simulaci fyzických systémů v Monte Carlu". Journal of Computational Physics. 97 (2): 566. Bibcode:1991JCoPh..97..566S. doi:10.1016 / 0021-9991 (91) 90015-D.
  17. ^ A b George, Marsaglia; Zaman, Arif (1991). „Nová třída generátorů náhodných čísel“. Annals of Applied Probability. 1 (3): 462–480. doi:10.1214 / aoap / 1177005878.
  18. ^ Martin, Lüscher (1994). "Přenosný vysoce kvalitní generátor náhodných čísel pro simulace teorie mřížových polí". Komunikace počítačové fyziky. 79 (1): 100–110. arXiv:hep-lat / 9309020. Bibcode:1994CoPhC..79..100L. doi:10.1016/0010-4655(94)90232-1.
  19. ^ Matthews, Robert A. J. (1992). „Maximálně periodické reciproční. Býk. Inst. Matematika. Appl. 28: 147–148.
  20. ^ Marsaglia, George; Zaman, Arif (1993). "Generátor KISS". Technická zpráva, ministerstvo statistiky, Florida State University, Tallahassee, FL, USA.
  21. ^ Příspěvek George Marsaglia v diskusní skupině sci.stat.math ze dne 1. srpna 2018 s názvem „Ještě další RNG '.
  22. ^ Koç, Cemal (1995). "Sekvence s opakováním". Journal of Applied Probability. 32 (4): 966–971. doi:10.2307/3215210. JSTOR  3215210.
  23. ^ Couture, Raymond; L'Ecuyer, Pierre (1997). "Distribuční vlastnosti generátorů náhodných čísel s násobením" (PDF). Matematika výpočtu. 66 Počet. 218 (218): 591–607. Bibcode:1997MaCom..66..591C. doi:10.1090 / S0025-5718-97-00827-2.
  24. ^ Matsumoto, M .; Nishimura, T. (1998). „MersenneTwister: A623-dimensionally Equidistributed Uniform Pseudo-Random Number Generator“. Transakce ACM na modelování a počítačové simulaci. 8 (1): 3–30. CiteSeerX  10.1.1.215.1141. doi:10.1145/272991.272995.
  25. ^ Marsaglia, Georgi (Červenec 2003). „Xorshift RNG“. Žurnál statistického softwaru. 8 (14). doi:10.18637 / jss.v008.i14.
  26. ^ Panneton, François O .; l'Ecuyer, Pierre; Matsumoto, Pierre (březen 2006). "Vylepšené generátory s dlouhou periodou založené na lineárních opakováních modulo 2" (PDF). Transakce ACM na matematickém softwaru. 32 (1): 1–16. CiteSeerX  10.1.1.73.5499. doi:10.1145/1132973.1132974.CS1 maint: ref = harv (odkaz)
  27. ^ Jenkins, Bob (2009). „Malý nekryptografický PRNG“.
  28. ^ A b C Salmon, John; Moraes, Mark; Dror, Ron; Shaw, David (2011). "Paralelní náhodná čísla: tak snadné jako 1, 2, 3". Sborník příspěvků z mezinárodní konference 2011 o vysoce výkonných počítačích, vytváření sítí, skladování a analýze, článek č. 16. doi:10.1145/2063384.2063405.
  29. ^ Steele, Guy L. Jr.; Lea, Doug; Flood, Christine H. (2014). "Rychlé rozdělitelné generátory pseudonáhodných čísel" (PDF). OOPSLA '14 Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages ​​& Applications.
  30. ^ O'Neill, Melissa E. (2014). „PCG: Rodina jednoduchých, rychlých, prostorově efektivních, statisticky dobrých algoritmů pro generování náhodných čísel“ (PDF). Technická zpráva.
  31. ^ Cookman, Richard (2016). "generátor bitů náhodného cyklu (rcb_generator)". Technická zpráva.
  32. ^ Widynski, Bernard (2017). "Middle Square Weyl Sequence RNG". arXiv:1704.00358v5 [cs.CR ].
  33. ^ Blackman, David; Vigna, Sebastiano (2018). "Zakódované lineární pseudonáhodné generátory". arXiv:1805.01407 [cs.DS ].
  34. ^ Harase, S .; Kimoto, T. (2018). „Implementace 64bitové verze Maximally Equidistributed F2-Lineární generátory s Mersenne Prime Period ". Transakce ACM na matematickém softwaru. 44 (3): 30:1–30:11. arXiv:1505.06582. doi:10.1145/3159444.
  35. ^ Widynski, Bernard (2020). „Squares: a Fast Counter-Based RNG“. arXiv:2004.06278v2 [cs.DS ].
  36. ^ Generátor skutečných náhodných čísel využívající absolutorium Corona: Indický patentový úřad. Číslo patentové přihlášky: 201821026766
  37. ^ Thomas Symul; Syed M. Assad; Ping Koy Lam (2011-06-07), „Demonstrace kvantového náhodného čísla v reálném čase s koherentním laserovým světlem v reálném čase“, Aplikovaná fyzikální písmena, 98 (23): 231103, arXiv:1107.4438, Bibcode:2011ApPhL..98w1103S, doi:10.1063/1.3597793

externí odkazy