Un generador de nombres pseudoaleatoris (GPAN) és un algorisme que produeix una successió de nombres que és una molt bona aproximació a un conjunt aleatori de nombres. La successió no és exactament aleatòria en el sentit que queda completament determinada per un conjunt relativament petit de valors inicials, anomenats estat del GPAN. Si bé és possible generar successions mitjançant generadors de nombres aleatoris amb dispositius mecànics que són millors aproximacions a una successió aleatòria, els nombres pseudo-aleatoris són importants en la pràctica per a certes simulacions (per exemple, de sistemes físics mitjançant el mètode de Montecarlo), i exerceixen un paper central en la criptografia.
La majoria dels algorismes de generadors pseudoaleatorios produeixen successions que posseeixen una distribució uniforme segons diversos tipus de proves. Les classes més comunes d'aquests algorismes són generadors lineals congruents, generadors Fibonacci demorats, desplaçaments de registre amb retroalimentació lineal i desplaçaments de registre amb retroalimentació generalitzada. Entre els desenvolupaments més recents d'algorismes pseudoaleatoris s'hi troben el Blum Blum Shub, el Fortuna, i el Mersenne twister.
Es requereix una acurada anàlisi matemàtica per tenir algun tipus de confiança en què un dau GPAN genera nombres que són prou "aleatoris" com per ser útils per al propòsit per al qual hom els necessita. Robert R. Coveyou del Laboratori Nacional d'Oak Ridge va escriure un article titulat, "La generació de nombres aleatoris és massa important com per ser deixada a l'atzar."[1] com John von Neumann deia de broma, "Tothom qui desenvolupa mètodes aritmètics per produir dígits aleatoris està per descomptat en pecat."[2]
A la pràctica, els resultats de molts GPAN presenten artefactes matemàtics que fan que els mateixos fallin en proves de detecció de paràmetres estadístics. Entre aquests s'inclouen,
- Períodes més curts que l'esperat per alguns estats llavor; en aquest context aquests estats llavor poden ser anomenats 'febles'
- Manca d'uniformitat de la distribució
- Correlació de valors successius
- Pobre distribució dimensional de la successió resultat
- Les distàncies entre l'ocurrència de certs valors estan distribuïdes de manera diferent que la que correspon a una successió aleatòria
- Algunes seqüències de bits són 'més aleatòries' que altres
Els defectes que són exhibits pels GPAN van des d'un rang del que imperceptible fins l'absolutament obvi. L'algorisme de nombres aleatoris Randu utilitzat durant dècades en grans ordinadors tipus mainframe tenia serioses deficiències, i com a conseqüència molt del treball de recerca produït en aquest període és menys fiable del que podria haver estat.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
