Vraag hoe werkt random () eigenlijk?


Elke taal heeft een random () functie of iets dergelijks om een ​​pseudo-willekeurig getal te genereren. Ik vraag me af wat er onder gebeurt om deze cijfers te genereren? Ik programmeer niets dat deze kennis nodig heeft, alleen maar om mijn eigen nieuwsgierigheid te bevredigen.


13
2017-08-31 20:41


oorsprong


antwoorden:


Het hele eerste hoofdstuk van Donald Knuth's baanbrekende  werk Seminumerieke algoritmen is opgenomen met het onderwerp van het genereren van willekeurige getallen. Ik denk echt niet dat een SO-antwoord in de buurt komt om de betrokken problemen te beschrijven. Lees het boek.


12
2017-08-31 20:45



Het blijkt verrassend eenvoudig om redelijk fatsoenlijke pseudo-willekeurige nummers te krijgen. De gouden standaard was decennia lang een opmerkelijk eenvoudig algoritme: houd stand X, vermenigvuldig met constant EEN (32x32 => 64 bits) en voeg vervolgens constant toe B, keer dan terug naar de lage 32-bits, die ook de nieuwe worden X. Als EEN en B zorgvuldig gekozen dit werkt eigenlijk redelijk goed.

Pseudorandom-getallen moeten ook herhaalbaar zijn om gedrag tijdens foutopsporing te reproduceren. Dus, de generator zaaien (initialiseren X met, laten we zeggen, de tijd van de dag), wordt meestal vermeden tijdens het debuggen.

In de afgelopen jaren, en met meer computercycli beschikbaar om te branden, zijn er meer geavanceerde algoritmen beschikbaar, waarvan sommige zijn uitgevonden sinds de publicatie van het overigens vrij autoritaire algoritme Seminumerieke algoritmen. Besturingssystemen beginnen ook hardware en netwerk-afgeleide entropiebits te leveren voor gespecialiseerde cryptografische doeleinden.


4
2017-08-31 20:59



De Wikipedia-pagina is een goede referentie.

Het gebruikte algoritme zal afhankelijk zijn van de taal en de implementatie van de taal.


4
2017-08-31 20:46



random () is een zogenaamde pseudorandoomnummergenerator (PRNG). random () wordt meestal geïmplementeerd als een lineaire congruente generator. Dit is een functie van de vorm X (n + 1) (aXn + c) modulo m. Xn is de reeks gegenereerde pseudo-willekeurige nummers. De gesynchroniseerde reeks getallen is gemakkelijk te raden. Dit algoritme kan niet worden gebruikt als een cryptografisch veilige PRNG.

Wikipedia: lineaire congruentiegenerator

En bekijk de Diehard-tests voor PRNG PRNG Diehard-tests


3
2017-08-31 20:54



Om precies antwoord te geven, wordt de willekeurige functie door het besturingssysteem geleverd (meestal).

Maar hoe het besturingssysteem deze willekeurige getallen creëert, is een gespecialiseerd gebied in de informatica. Zie bijvoorbeeld de wiki-pagina die in de bovenstaande antwoorden is geplaatst.


0
2017-08-31 20:49



Een ding dat je misschien zou willen onderzoeken, is de familie van willekeurige apparaten die beschikbaar zijn op sommige Unix-achtige besturingssystemen zoals Linux en Mac OSX. In Linux verzamelt de kernel bijvoorbeeld entropie van verschillende bronnen in een pool die het vervolgens gebruikt om zijn pseudo-willekeurige nummergenerator te seeden. De entropie kan afkomstig zijn uit verschillende bronnen, waarvan de belangrijkste zijn jitter van het apparaatstuurprogramma van toetsaanslagen, netwerkgebeurtenissen, activiteit van de harde schijf en (vooral) muisbewegingen. Afgezien hiervan zijn er andere technieken om entropie te verzamelen, waarvan sommige zelfs volledig in hardware zijn geïmplementeerd. Er zijn twee karakter-apparaten waar je willekeurige bytes van en op Linux kunt krijgen, ze gedragen zich op de volgende manier:

  • / dev / urandom geeft je een constante stroom van bytes die erg willekeurig is maar niet cryptografisch veilig omdat het hergebruikt welke entropie er in het zwembad beschikbaar is.
  • / dev / random geeft je cryptografisch veilige willekeurige getallen, maar het geeft je geen constante stroom omdat het de entropie gebruikt die beschikbaar is in de pool en vervolgens blokkeert terwijl meer entropie wordt verzameld.

Merk op dat terwijl Mac OSX een andere methode gebruikt voor zijn PRNG en daarom niet blokkeert, mijn persoonlijke benchmarks (gedaan op de universiteit) hebben aangetoond dat het allemaal-zo-iets minder willekeurig is dan de Linux-kernel. Zeker goed genoeg.

Dus, in mijn projecten, wanneer ik willekeur nodig heb, ga ik meestal voor het lezen van een van de willekeurige apparaten, althans voor het zaad voor een algoritme in mijn programma.


0
2017-09-01 00:55