Random generator

[descheleschilder]

Hoe is het mogelijk een programma te schrijven dat als output een willekeurig getal produceert (bijvoorbeeld van 1 tot en met 10)? Zijn random en programmeren niet als vuur en water? Hoe kun je het gedrag van bijvoorbeeld een dobbelsteen programmeren? Moet er in het programma niet gebruik worden gemaakt van een werkelijke random gebeurtenis?

[rwwh]

Inderdaad kan dat niet. Je kunt alleen een "pseudo-random" getal genereren. Wat ze wel proberen is om de omgeving mee te rekenen, bijvoorbeeld ruis die wordt opgepikt door de muis of de microfoon. In elk geval is dit zo moeilijk om goed te doen dat het verstandig is om een goede functie uit te kiezen uit een bibliotheek, die ook volgens de gebruiksaanwijzing geschikt is voor het doel dat je wilt bereiken.
Zie ook http://en.wikipedia.org/w/index.php?title=Pseudorandom_number_generator

[descheleschilder]

Wat bedoel je percies met dat laatste:
 

In elk geval is dit zo moeilijk om goed te doen dat het verstandig is om een goede functie uit te kiezen uit een bibliotheek, die ook volgens de gebruiksaanwijzing geschikt is voor het doel dat je wilt bereiken.

Zie ook http://en.wikipedia.org/w/index.php?title=Pseudorandom_number_generator

[Typhoner]

Hij bedoelt dat, typisch gezien, programmeurs die random getallen nodig hebben een bestaande code "inpluggen" in hun programma. De goede generators (van het moment) zijn al lang en breed beschreven in de literatuur en de optimale implementaties zijn, nu ja, optimaal dus zelf iets in elkaar flansen in geen goed idee behalve als je gewoon interesse hebt in het gebied en eens wil spelen, maar voor serieuze toepassingen vertrouw je op bestaande implementaties.
 
In ieder geval heeft elke pseudo-random generator zijn zwaktes, omdat er altijd een zeker patroon zal zijn de "stroom" getallen die deze genereert. Dus de vraag is: wat vind je acceptabel? Wat zijn de voorwaarden die je wel of niet wil stellen? Dat hangt natuurlijk af van het exacte doel: wil je aan cryptografie doen, Monte Carlosimulaties uitvoeren, een loterij organiseren, etc. Je moet dus de handleiding van de PRNG lezen om te zien of hij geschikt is voor jouw doel. Voor wetenschappelijke toepassingen lijkt de Mersenne Twister tegenwoordig het meest gebruikt, alhoewel PRNG's van Marsaglia of die van Lehmler nog vaak te vinden zijn.
 
Overigens kan je op http://www.random.org/ wél echte random getallen genereren: de site gebruikt daarvoor een set radio's die atmosferische ruis opvangen die dan wordt geconverteerd naar getallen. Uiteraard is deze methode niet zo bruikbaar voor programmeertoepassingen die "on the fly" miljoenen getallen nodig hebben.
 
Het dient te worden opgemerkt dat "random" sowieso heel moeilijk te verifiëren is: er kan altijd een patroon zijn, maar misschien zie je het juist niet in jouw sample.
 

 
Dit geldt voor zowel PRN's als "echte". Voor PRN's is de uitspraak van von Neumann nog steeds relevant:
 
Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin

[Math-E-Mad-X]

 Dus de vraag is: wat vind je acceptabel? Wat zijn de voorwaarden die je wel of niet wil stellen? Dat hangt natuurlijk af van het exacte doel: wil je aan cryptografie doen, Monte Carlosimulaties uitvoeren, een loterij organiseren, etc. Je moet dus de handleiding van de PRNG lezen om te zien of hij geschikt is voor jouw doel. 
 

 
Als je een loterij wil organiseren is dit inderdaad extreem belangrijk.
 
Ik meen ooit een krantebericht gelezen te hebben waarin stond dat hackers het algoritme achter krasloten hadden gekraakt. Ze konden dus aan de hand van het lotnummer nagaan of er een prijs op het kraslot stond. Blijkbaar had de organisator een te simpele random number generator gebruikt.
Overigens heb ik ook weleens van een quantum random number generator gehoord. Een apparaatje dat echte random numbers genereert,  omdat hij gebruikt maakt van toevallige quantum events.

[Flisk]

Er zijn twee soorten generators, pseudo en true. Pseudo random generators hebben een periode en de nummers die eruit komen zijn volledig bepaald en in één bepaalde volgorde. Dit soort generatoren zijn vrij simpel te programmeren en wordt dus heel vaak gebruikt wanneer veiligheid geen issue is. Voorbeeld is de lineaire-congruentiegenerator. Bekijk deze topic eens. Er staat een voorbeeldje in.

True random generators maken meestal idd gebruik van random fysische processen.

[Benm]

Er zijn diverse methodes om random getallen te genereren. Pseudorandom is wel de meest gebruikelikje gezien je daarvoor geen speciale hardware nodig hebt. Het is een voorspelbare reeks waarden die gegeven worden, maar die reeks kan zeer lang zijn, en je kunt het beginpunt binnen die reeks vaak wel kiezen.

Wat wel eens gedaan wordt is deze sequentie gebruiken, maar beginnen op een punt dat afhankelijk is van microtime (tijd op 1 ms nauwkeurig) waardoor het telkens een andere reeks oplevert. Maar als je de exacte tijd weet kun je exact voorspellen welke getallen de code zal produceren, en als je het bijv op 1 seconde nauwkeurig weet kun je 1000 mogelijke reeksen (re)produceren waarvan er eentje zal kloppen.

Nieuwere processors hebben overigens vaak wel een betere random generator aan boord, bijvoorbeeld RdRand op intel processors vanaf ivy bridge. Hoewel deze niet onfeilbaar zijn, zijn ze aanzienlijk beter dan pseudorandom generatoren omdat ze gebruik maken van bijv de ruis over een diode om wat echte entropie te verkrijgen.

Uiteraard zijn er meerdere manieren om aan entropie te komen, bijvoorbeeld het pingen van een aantal servers en de tijd die dat kost te gebruiken. Ook dingen als exacte muisbewegingen worden gebruikt (bijvoorbeeld door truecrypt) - hoewel die niet extreem veel entropie hebben is het veel lastiger zoiets te reproduceren vergeleken met pure pseudorandom.

[luc]

Er zijn machines die dobbelstenen rollen en met behulp van een camera opslaan wat er gerold is. Dit heb ik wel eens bij ‘how do they do it’ gezien voor online casino’s en automaten. Dat filmpje kan ik helaas niet terug vinden en kan momenteel geen Youtube video’s afspelen maar aan de beschrijving te zien bedoel ik dit: https://www.youtube.com/watch?v=7n8LNxGbZbs

[Benm]

Tja, das ook een manier, en zal wel tot de verbeelding spreken. Wat echter veel meer entropie oplevert is het hele webcambeeld gebruiken ipv proberen te getallen op de dobbelstenen uit te lezen.

Iets dergelijks is ook wel eens gedaan met een lavalamp... sterker nog, dat is gepatenteerd http://www.google.com/patents/US5732138

[descheleschilder]

Alle fysische manieren om een random getal te genereren gelden alleen in een perfecte fysische wereld. De dobbelsteen moet perfect symmetrisch zijn, ruis (waarmee ik entropie bedoel zonder door mensen daarin gezette informatie) moet geproduceerd worden door perfect isotropische entropie.Neem bijvoorbeeld een Browns deeltje; je zou denken dat dat deeltje zich in een vloeistof bevindt die het deeltje puur willekeurige stootjes geeft, omringd door homogene entropie, hetgeen een idealisatie is. Zelfs het meten van de plaats van identieke deeltjes (ook een idealisatie) zal op den duur een hele lichte voorkeur voor een bepaalde plaats laten zien (percentueel gezien Natuurlijk, aangezien een groot aantal metingen een duidelijke voorkeur geven aan de plek waar de absolute waarde van de golffunctie het grootst is)), aangezien de meetapparatuur enige "bias" zal vertonen.

[Benm]

Er bestaan tests voor de 'randomness' van een gegeven bitstream. Als je een lange stream vraagt zullen pseudorandom generators altijd falen, aangezien die op een gegeven punt weer van het begin af aan beginnen.

De echte tests zijn vrij uitgebreid en bekijken diverse aspecten, maar je kunt het zelf ook vrij eenvoudig testen. Als je bijvoorbeeld een flink stuk random data genereert (zeg 100 MB ofzo) en dat probeert te comprimeren (met 7zip op 'maximum' oid), dan zal het nauwelijks kleiner worden als de data echt random is.

Neem je iets dat niet echt random is, bijvoorbeeld een rauw audiobestand, zul je zien dat er enige compressie mogelijk is (tot bijv 70% van het oorspronkelijke formaat).

Let wel dat dit geen echte 'randomness test' is - dingen die al gecomprimeerd zijn (mp3s, videos, zipfiles etc) worden niet kleiner terwijl ze absoluut niet random zijn.

[Typhoner]

En dus, opnieuw: alvorens je (pseudo)random getallen wenst te gebruiken moet je eerst duidelijke eisen stellen, in principe tezamen met een bruikbare procedure om te verifiëren of een generator hieraan voldoet. Marsaglia's DIEHARD-testen zijn nogal oud, maar vormen een nuttig middel op random getallen voor wetenschappelijk/technische doeleiden (Monte Carlo-simulaties bijvoorbeeld) te testen op bepaalde eigenschappen.