Hoe creeert een computer een random getal

[Koeniepoenie]

Omdat ik nogal eens aan het programmeren ben, vroeg ik me af hoe een computer een random getal laat generen.
Ik heb de search gebruikt, en vond een topic over Computers en random getallen, en nog een over willekeurigheid bestaat. Maar dat gaf niet echt een goed antwoord op mijn vraag.

Over willekeur heeft ieder zijn ideeen natuurlijk, maar ik ben overtuigd van het feit dat willekeurigheid niet bestaat, hoogstens in de kwantummechanica, en dus kon ik me niet bedenken hoe een computer een 'random' getal maakt.

Want een computer kan nou eenmaal niet zeggen van 'laat ik nu die eens nemen'. Het moet een bepaald patroon volgen, maar welke?

[ Voor 8% gewijzigd door Koeniepoenie op 16-08-2004 21:34 ]

[NMe]

Willekeurigheid bestaat niet voor computers. Als je in Pascal of C bijvoorbeeld een random getal laat maken zonder eerst te randomizen, dan krijg je steeds als je het programma opnieuw opstart dezelfde waarden.

Hoe je een goed semi-random getal maakt heb ik ooit geweten, maar nu niet meer. Er zijn in ieder geval leuke formules voor, die je op Google vast kan vinden.

Willekeurigheid bestaat dus wel, alleen snapt een computer dat niet.

[Johnny]

Het maken van random getallen is inderdaad een van de moeilijkste dingen die er is.

Als je programmeert zal de computer vaak het random getal op de huidige datum en tijd baseren, en daar nog wat andere omgevingsvariablen en daar berekeningen op los laten.

Vaak is het ook mogelijk om een zogenaamde "seed" op te geven, een extra getal dat in de "random" berekening wordt meegenomen waardoor de kans groter is dat je uitkomst uniek is (als je de seed steeds veranderd).

[Verwijderd]

Random getallen zijn eigenlijk pseudo random getallen.

Ik denk dat er op HowStuffWorks wel iets over te lezen is, ben niet zeker. De basis is alleszins gebaseerd op modulo-rekening. De computer start met een vast getal en voert daar modulo-rekening op uit met een hele grote modulus. Dat bekomen getal vormt dan de basis voor het volgende random getal. Zo komt er soort random getal tot stand. Verder kan er ook nog gebruik gemaakt worden van het uur of datum etc om iets willekeuriger te werken.

[Koeniepoenie]

NMe84 schreef op 16 augustus 2004 @ 21:36:
Willekeurigheid bestaat niet voor computers. Als je in Pascal of C bijvoorbeeld een random getal laat maken zonder eerst te randomizen, dan krijg je steeds als je het programma opnieuw opstart dezelfde waarden.

Neej ok, daar was ik achter, maar hoe 'doen ze alsof' ze een willekeurig getal maken dan?

Willekeurigheid bestaat dus wel, alleen snapt een computer dat niet.

Waar vind jij willekeurigheid dan?
Maar goed, dat wijkt af van 't topic

[Zoijar]

Meestal begin je idd met een vast getal, een 'seed', en daarmee gebruik je een chaotische functie. Computer random wordt dan ook wel semi-random (of pseudo) genoemd, omdat er vaak een lichte mate van voorspelbaarheid in zit.

Echt random wordt volgens mij op het moment vooral gedaan dmv het meten van atmosferische ruis. (er staat me ook iets bij over het meten van het verval van onstabiele isotopen.)

[ Voor 15% gewijzigd door Zoijar op 16-08-2004 21:41 ]

[Microkid]

Ik dacht dat er iig gerekend werd met de kloktijd (miliseconden) en een formule waardoor er steeds andere waarden uitrollen.

[Henk007]

Echte random getallen zijn het niet, meestal wordt dat pseudo-random genoemd.
Daarbij wordt gebruik gemaakt van funkties die een zo grillig verloop hebben dat het lijkt alsof de uitkomst willekeurig is.
Verder heeft iedere randomgenerator een 'seed' nodig. Anders zou het eerste willekeurige getal na het opstarten steeds hetzelfde zijn, want als f(x)=a blijft dat zo voor dezelfde x, hoe grillig verloop f(x) ook heeft.
Voor deze seed maakt men gebruik van timers eventueel in combinatie met user input (aantal millisec tussen 2 toetsaanslagen of zo).
Het wiskundig analyseren van de kwaliteit van een random generator is nog een vak apart trouwens.

Edit:
Woei, de search werkt weer:
Computers en random getallen?
Hoe kiest de computer een random nummer?
Random getallen

[ Voor 17% gewijzigd door Henk007 op 16-08-2004 21:53 ]

[glashio]

NMe84 schreef op 16 augustus 2004 @ 21:36:
Als je in Pascal of C bijvoorbeeld een random getal laat maken zonder eerst te randomizen, dan krijg je steeds als je het programma opnieuw opstart dezelfde waarden.

Hoe je een goed semi-random getal maakt heb ik ooit geweten, maar nu niet meer.

code:

seed(unix timestamp)

^{C of Pascal syntax is mij niet bekend}

Het ligt eraan hoe diep in gradatie de random moet zijn (ivm floatingpoint berekeningen).
Dit is de ultieme "Random Seeder" ( maar gebruikerhandeling afhankelijk )

[SysRq]

Microkid schreef op 16 augustus 2004 @ 21:40:
Ik dacht dat er iig gerekend werd met de kloktijd (miliseconden) en een formule waardoor er steeds andere waarden uitrollen.

Als je het zo stelt is het dus totaal niet random: de dezelfde kloktijd en de formule geven dus iedere keer dezelfde waarde terug.

Zoijar schreef op 16 augustus 2004 @ 21:39:
Echt random wordt volgens mij op het moment vooral gedaan dmv het meten van atmosferische ruis. (er staat me ook iets bij over het meten van het verval van onstabiele isotopen.)

Kun je aantonen dat atmosferische ruis 'echt' random is? Dat _wij_ er geen partoon in kunnen zien wil natuurlijk nog niet zeggen dat het volledig random is.

[Zoijar]

SysRq schreef op 16 augustus 2004 @ 21:45:
Kun je aantonen dat atmosferische ruis 'echt' random is? Dat _wij_ er geen partoon in kunnen zien wil natuurlijk nog niet zeggen dat het volledig random is.

Nou...ja en nee. Statistisch is het random. Er zit natuurlijk een patroon achter, maar dat is zo complex dat het niet te beschrijven is, en waarschijnlijk ook niet turing computable is.

Heb het even nagezocht en idd de drie waar ik al aan dacht (radioactiviteit, ruis, lavalamps)

A really good source of entropy is a radioactive source. The points in time at which a radioactive source decays are completely unpredictable, and can be sampled and fed into a computer, avoiding any buffering mechanisms in the operating system. In fact, this is what the HotBits people at Fourmilab in Switzerland are doing. Another source of entropy could be atmospheric noise from a radio, like that used here at random.org, or even just background noise from an office or laboratory. The lavarand people at Silicon Graphics have been clever enough to use lava lamps to generate random numbers, so their entropy source not only gives them entropy, it also looks good! The latest random number generator to come online (both lavarand and HotBits precede random.org) is Damon Hart-Davis' Java EntropyPool which gathers random bits from a variety of sources including HotBits and random.org, but also from web page hits received by the EntropyPool's web server.

-- random.org

[Verwijderd]

Zoijar schreef op 16 augustus 2004 @ 21:47:
[...]
niet turing computable is.

En waarom is dat?

/me is heel benieuwd hoe Zoijar zich hier uit redt.

[MSalters]

Quantum mechanica en chaos effect. Niet alleen de spreekwoordelijke vlinder kan een storm tot gevolg hebben, maar ook een spontaan deeltjespaar.

Overigens werk ik in dit soort zaken bij voorkeur niet met wiskundige, maar fysische modellen van de grenzen. Een probleem is dan niet Turing-computable als 10⁸⁰ gates in 10⁴² klokcycli het niet kunnen uitrekenen. Dat is veel minder dan oneindig

[Zoijar]

Ja, MSalters legt het eigenlijk al uit. Bovendien type ik voor dat soort uitspraken (op gevoel) altijd iets als 'waarschijnlijk' om mezelf in te dekken; dan zit je meestal wel goed

Verder denk ik dat je om alle atmosferische ruis op aarde exact uit te rekenen, zo goed als een simulatie van het universum moet hebben. Het moge duidelijk zijn dat als bepaalde (simpele) problemen al niet turing compatible zijn, dat een simulatie van het universum dat zeker niet is. Bovendien zou je hier een simulatie zo groot als het universum zelf voor nodig hebben, ofwel het universum zelf. En dan nog het 'god plays dice' probleem... Hoe ga je berekenen op een turing machine wanneer een radioactief deeltje vervalt? Hoewel je wel kan optimaliseren etc. en zo misschien al mijn argumenten van tafel kan vegen, heb ik intuitief het gevoel dat het een onmogelijke opgave zal zijn.

Wat wel eventueel zou kunnen is een statistisch model opstellen van ruis op aarde, en daar met behulp van gegeven voorwaarden (datum van meting, positie aarde, etc) genoeg voorspellingen over kunnen doen om het pseudo random te maken.

[Mx. Alba]

MSalters schreef op 16 augustus 2004 @ 23:47:
Quantum mechanica en chaos effect. Niet alleen de spreekwoordelijke vlinder kan een storm tot gevolg hebben, maar ook een spontaan deeltjespaar.

Fout.

Een anti-deeltje is eigenlijk een heel gewoon deeltje, maar het gaat terug in de tijd. Er ontstaan dus niet zomaar uit het niets een deeltje en een anti-deeltje! Het anti-deeltje komt "tegen de tijd in" aan, en wordt omgezet in een gewoon deeltje, dat weer met de tijd mee weg gaat. Vanuit ons tijdgebonden oogpunt lijkt het dus alsof uit het niets een deeltje en een anti-deeltje ontstaan, maar dat is dus niet zo.

Een deeltje en een anti-deeltje dat elkaar opheffen werkt het zelfde. Er komt een deeltje aangewandeld, met de tijd mee, die dan zijn tijdcomponent omkeert en dus een anti-deeltje wordt, dat terug in de tijd gaat. Voor ons lijkt het alsof een deeltje en een anti-deeltje opelkaar botsen en compleet verdwijnen, maar de werkelijkheid is dus anders.

[/offtopic]

Voor zover ik weet is de beste bron voor willekeurigheid het verval van radio-actieve kernen, zoals al eerder gezegd trouwens. (Spuit 13?)

[Dido]

Een simpel algoritme dat ik ooit eens ergens heb gezien ging simpelweg uit van het kwadrateren en vervolgens links en rechts trimmen van een viercijferig getal.
Uiteraard ben je ook hier afhankelijk van je seed, en hoe goed de gegenereerde getallen de statistische criteria voor willekeurigheid doorstaan weet ik niet

Onvoorspelbare functies zijn er genoeg, het lijkt me bijvoorbeeld niet al te moeilijk om punten uit bijvoorbeeld de Lorentz-attractor te gebruiken. Je bent nog steeds afhankelijk van je seed, maar aangezien een miniscuul kleine afwijking van je beginwaarde al onvoorspelbare gevolgen heeft zou je bij het bepalen van je seed (of in het geval van een Lorentz-attractor drie seeds) gebruik kunnen maken van de onnauwkeurigheid van je hardware.

[Verwijderd]

Onvoorspelbare functies zijn er genoeg, het lijkt me bijvoorbeeld niet al te moeilijk om punten uit bijvoorbeeld de Lorentz-attractor te gebruiken.

Precies. Met nonlineaire ruis, bijvoorbeeld dmv een Duffing oscillator, Chua's oscillator oid als basis kom je al een heel eind. En als je reden voor onwillekeurigheid encryptie is, daarvoor zijn zelfs gespecialiseerde componenten: http://www.anafocus.com/Folletos/AFM3103a.pdf

[ Voor 3% gewijzigd door Verwijderd op 17-08-2004 08:19 ]

[Confusion]

Mx. Alba schreef op 17 augustus 2004 @ 07:10:
Een anti-deeltje is eigenlijk een heel gewoon deeltje, maar het gaat terug in de tijd.

Waar komt deze informatie vandaan en hoe moet ik dat interpreteren?

Er ontstaan dus niet zomaar uit het niets een deeltje en een anti-deeltje!

Virtuele deeltjesparen die uit het niets ontstaan zijn, zoals de naam al zegt, virtueel, en zijn op geen enkel moment echte deeltjes: ex nihilo nihil fit. Bij deeltjesbotsingen in deeltjesversnellers, zoals CERN, komen echter wel degelijk antideeltjes vrij, die je vervolgens ook rustig een tijdje in een magnetisch val op kunt sluiten. Die reizen niet terug in de tijd en vervallen zeker niet in 'gewone' deeltjes. Een electron en een positron (anti-electron) kunnen zelf voor korte tijd het zogenaamde positronium vormen: een gebonden toestand van de twee, dat lijkt op waterstof, met het verschil dat het instabiel is. De twee zullen elkaar annihileren, waarbij energie vrijkomt.

Een deeltje en een anti-deeltje dat elkaar opheffen werkt het zelfde. Er komt een deeltje aangewandeld, met de tijd mee, die dan zijn tijdcomponent omkeert en dus een anti-deeltje wordt, dat terug in de tijd gaat. Voor ons lijkt het alsof een deeltje en een anti-deeltje opelkaar botsen en compleet verdwijnen, maar de werkelijkheid is dus anders.

Nou, volgens mij is de werkelijkheid helemaal niet anders, maar is jouw versie een andere interpretatie van dezelfde wiskunde. Maar hoe de wiskunde fysische geinterpreteerd dient te worden is niet duidelijk en het is zeker niet gangbaar om te accepteren dat 'de tijdscomponent van het deeltje' 'omgedraaid' wordt. Het is niet eens duidelijk wat dat precies zou moeten betekenen in 'de werkelijkheid'.

Edit: Tenzij je het in termen van Feynman diagrammen bedoeld, maar dan nog...

[ Voor 5% gewijzigd door Confusion op 17-08-2004 17:39 ]

[Karel V]

Zoijar schreef op 16 augustus 2004 @ 21:39:
[...]
Echt random wordt volgens mij op het moment vooral gedaan dmv het meten van atmosferische ruis. (er staat me ook iets bij over het meten van het verval van onstabiele isotopen.)

Mij staat ook iets bij van ruis.
Zou dat ook niet bij je poorten gemeten kunnen worden. Ik herinner me dat er daar altijd wel hele kleine ruisspanningen heersen, die zo goed als random heen en weer flippen (in storende omgevingen).

[Verwijderd]

Een voorbeeld van een random number generator die was ooit nog een oefening was. Ik kan geen exacte verklaring geven voor de beginwaardes, al lijkt het mij logisch dat grotere waardes een grilliger verloop opleveren en dat de waardes onderling best relatief priem zijn.

code:

;;;initialisatie
modulogetal= - 2^32
vermeningvuldiggetal= 7^5
seed= 97

;;eigenlijke code

function random:
            ;;;seed krijgt een nieuwe random waarde
           seed = modulus(seed*vermenigvuldiggetal),modulogetal)

            ;;;zorgen dat het getal teruggeven tussen 0 en 1 ligt
           return  seed/modulogetal

[caipirinha]

Voor een goede uitleg over pseudorandomgetallen kun je "The art of computer programming" deel 2 van Donald E Knuth lezen. Heb ik zelf veel van geleerd. ISBN 0-201-89684-2. Is redelijk taai.
Echte randomgetallen kun je genereren met een ruisende diode en een a/d converter.
De nieuwe VIA mini ITX bordjes hebben zo´n generator in de processor ingebouwd, Heb geen flauw idee hoe goed deze is.

[MSalters]

Confusion schreef op 17 augustus 2004 @ 10:03:
[...]
Virtuele deeltjesparen die uit het niets ontstaan zijn, zoals de naam al zegt, virtueel, en zijn op geen enkel moment echte deeltjes: ex nihilo nihil fit

Als je Wikipedia quote, quote dan op z'n minst het relevante artikel:
virtual particles
Daar staat inderdaad dat externe energie het deeltjespaar uit elkaar kan drijven. Nou, de atmosfeer mag dan een gas zijn, maar er zijn nog genoeg deeltjes en dus genoeg energie om een enkel deeltjespaar uit elkaar te drijven, dus dat draagt zeker bij aan de onvoorspelbaarheid van de atmosfeer.

[Vaughn]

Johnny schreef op 16 augustus 2004 @ 21:37:

Het maken van random getallen is inderdaad een van de moeilijkste dingen die er is.

Als je programmeert zal de computer vaak het random getal op de huidige datum en tijd baseren, en daar nog wat andere omgevingsvariablen en daar berekeningen op los laten.

Vaak is het ook mogelijk om een zogenaamde "seed" op te geven, een extra getal dat in de "random" berekening wordt meegenomen waardoor de kans groter is dat je uitkomst uniek is (als je de seed steeds veranderd).

Maken van random getallen is zo moeilijk niet... Je zou met radio activiteit iets kunnen doen i.c.m. geigerteller op de computer. Radio actief verval is namelijk geheel willekeurig.

[Witte]

Is wel heel moeilijk. Bij Random getallen moet namelijk elk getal een even grote kans hebben om voor te komen. Verder moet elke combinatie van 2 getallen ook een even grote kans hebben, en zo kan je door gaan.

[Confusion]

MSalters schreef op 17 augustus 2004 @ 22:34:
Daar staat inderdaad dat externe energie het deeltjespaar uit elkaar kan drijven. Nou, de atmosfeer mag dan een gas zijn, maar er zijn nog genoeg deeltjes en dus genoeg energie om een enkel deeltjespaar uit elkaar te drijven,

Zoals op die wikipedia pagina te lezen valt, gebeurt dat alleen bij bijvoorbeeld zwarte gaten, waarbij het deeltje netto uit het zwarte gat verdwijnt. In de atmosfeer is geen bron voor massa of energie en zal geen enkel virtueel deelje reeel worden. De virtuele deeltjesparen die zich om ons heen vormen annihileren elkaar met een netto effect van 0 op de omgeving (zelfs als 1 paar een effect zou kunnen hebben, zijn het er zo ontzettend veel dat het statistisch voor alle praktische overwegingen 0 oplevert).