Random nummer generator

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Reageer
Berichten: 8

Random nummer generator

Goedenmiddag,

(mijn eerste post!)

Ik heb een zeer snelle random nummer generator gemaakt, alleen krijg ik maar geen grip erop om te zien of mijn nummer generator nu ook daadwerkelijk random is. Ik heb op Wikipedia (internet) gekeken en ik kom dan uit op de Monte Carlo project, echter is er maar 1 voorbeeld wat eigenlijk geen voorbeeld is. Is er iemand die mij hiermee kan helpen? Of mij de weg kan wijzen bij wie/wat/waar?

Groetjes, Dippo

Gebruikersavatar
Berichten: 419

Re: Random nummer generator

Stel: de generator levert getallen op tussen de 1 en de 10 (1, 2, 3, ... , 9, 10). Laat de generator bijv. 1000 keer draaien, en noteer welke getallen hij geeft. Na 1000 keer zou elk getal ongeveer 100 keer moeten zijn genoteerd, mits de generator random is.

Het is natuurlijk (bijna) ondoenlijk om dit handmatig te doen, maar ik neem aan dat je jouw generator in een programma kan gebruiken en dan kan je natuurlijk een programma maken om de waarden te noteren.

Groet,

Korot
Kijk ook eens op het Distributed Computing forum en doe mee met BOINC!

http://www.wetenschapsforum.nl/index.php?showforum=59

Gebruikersavatar
Berichten: 2.097

Re: Random nummer generator

Dit is meer iets voor het wiskundeforum
"Why must you speak when you have nothing to say?" -Hornblower

Conserve energy: Commute with a Hamiltonian

Gebruikersavatar
Moderator
Berichten: 4.087

Re: Random nummer generator

Slechts de frequentie checken is niet voldoende voor een goede random number generator. Kijk ook eens op Wikipedia of op andere sites die er dieper op ingaan.

Berichten: 8

Re: Random nummer generator

Dank voor de snelle respons. Ik heb een programma gemaakt wat telt hoeveel keer een getal is gevallen, echter (wat je zelf ook aangeeft) de uitkomst is tevens random. (4 getallen, 400 keer raden)

R1 : 92 must be:95 or 101 or 112

R1 : 106 must be:101 or 94 or 99

R1 : 90 must be:113 or 110 or 87

R1 : 110 must be:98 or 104 or 88

R1 : 104 must be:98 or 101 or 97

R1 : 105 must be:100 or 91 or 104

R1 : 79 must be:116 or 104 or 101

R1 : 110 must be:96 or 91 or 103

R1 : 106 must be:94 or 103 or 97

R1 : 93 must be:108 or 97 or 102

R1 : 103 must be:103 or 93 or 101

Daar zit ook een beetje het probleem, wat is nu random? ;)

En klopt het dat dit onder wiskunde valt?

Bvd, Dippo

Gebruikersavatar
Berichten: 5.679

Re: Random nummer generator

Spreekt voor zich, maar 'daadwerkelijk' random is het natuurlijk per definitie nooit. Er zit een algoritme achter, dus het volgende getal is met 100% zekerheid te voorspellen (mits je het algoritme kent).

Perfecte 'pseudo-randomness' is wat je hier wilt, en dat wil zoveel zeggen als geen enkele detecteerbare correlatie binnen de data die eruit komt. Dat is een erg ingewikkeld criterium om te testen, hier zijn een paar opties:

http://www.random.org/analysis/

http://csrc.nist.gov/groups/ST/toolkit/rng/ (met downloadbare randomness-test-software)

http://www.fourmilab.ch/random/ (een ander randomness-test-programmaatje)

Een eenvoudige test die je zo zelf kunt uitvoeren is om een paar MB aan data te genereren met je randomgenerator, en dat proberen te comprimeren (met bijvoorbeeld zip, rar of 7z). Als er minder dan 99.99% van overblijft is je randomgenerator niet goed.
In theory, there's no difference between theory and practice. In practice, there is.

Berichten: 8

Re: Random nummer generator

Dank u, ik heb naar de links gekeken, maar ik begrijp de software niet zo. Daarnaast kon ik ook geen executable vinden bij de NIST. Documentatie bij de software is er niet. Ik zal nog eens goed kijken op de websites.

De zip test heb ik gedaan, ik heb een noise image gemaakt en deze opgeslagen als TIF. Hij comprimeert maar 50%.

Een andere noise image met alleen zwart of wit, comprimeert weer wel 90%. Ik denk ook niet dat dit een goede test is, de andere noise image had wel alle kleuren van de regenboog.

Op de website http://en.wikipedia.org/wiki/Statistical_randomness staan een aantal tests die ik Java geprogrammeerd heb. De gap test heb ik moeite mee om dit te vertalen. De poker test heb ik alsvolgt vertaald: 5 random nummer die 0 of 1 kunnen zijn, voor ieder getal die positief is wordt een waarde verhoogd met 1. Na verloop van tijd worden de uitkomsten (winnaars) weer bij elkaar opgeteld en zal de test opnieuw beginnen. Het uiteindelijke verschil moet 5% zijn.

Mag ik anders de java source posten om te zien of ik het goed gemaakt heb? Het is welliswaar in Java Processing gemaakt, maar is simpel te vertalen naar standaard Java.

Bvd, Dippo.

Gebruikersavatar
Berichten: 5.609

Re: Random nummer generator

Dippo schreef:De zip test heb ik gedaan, ik heb een noise image gemaakt en deze opgeslagen als TIF. Hij comprimeert maar 50%.

Een andere noise image met alleen zwart of wit, comprimeert weer wel 90%. Ik denk ook niet dat dit een goede test is, de andere noise image had wel alle kleuren van de regenboog.
Hmm, het is het eenvoudigst als je gewoon een binary file uitschrijft. Zorg dat je pseudorandomgenerator eerst willekeurige bytes maakt (=getallen tussen 0 en 255). Die kun je wegschrijven met een [snapback]655197' target='_self[/snapback]<div class='quotemain'><!--quotec-->Op de website [snapback]655197' target='_self[/snapback]<div class='quotemain'><!--quotec-->Mag ik anders de java source posten om te zien of ik het goed gemaakt heb? Het is welliswaar in Java Processing gemaakt, maar is simpel te vertalen naar standaard Java.[/quote]

Je kunt ze hier altijd in bijlage bij je bericht plaatsen. Of als het niet te lang is tussen

Code: Selecteer alles

-tags in je bericht
What it all comes down to, is that I haven't got it all figured out just yet

And I've got one hand in my pocket and the other one is giving the peace sign

-Alanis Morisette-

Gebruikersavatar
Berichten: 5.679

Re: Random nummer generator

Die tests die op die wiki page worden beschreven (zoals de gap test en poker test die je noemt) zijn inderdaad vrij zwak en zeer willekeurig.

Verderop werd wel de 'diehard' getest genoemd, die ik me nu weer herinner van lang geleden, die was al een stuk beter (hier te downloaden). Ik zie dat er sinds enige tijd ook een 'dieharder' test is: http://www.phy.duke.edu/~rgb/General/dieharder.php

Ik heb deze versie zelf nog niet getest, maar daar zou ik zeker even mee experimenteren.
In theory, there's no difference between theory and practice. In practice, there is.

Berichten: 8

Re: Random nummer generator

317070, ja, ik had die laatste zin er niet bij moeten schrijven.

Rogier, ik ga zeker eens naar die links kijken. De standaard tests gaven mij wel inzicht om mijn tests visueel te maken. In Java Processing kan ik heel makkelijk het scherm vullen met kleurtjes. Kleurtjes zeggen eenmaal meer dan getallen.

Ik heb de 7zip test gedaan, maar ik twijfel weer. Ik heb gedaan wat 317070 zei, maar met 255 byte getallen is met mijn random generator en die van standaard Java, is de compressie 0%!

Bij 64 byte getallen komen er tenminste wel een compressie naar voren in winrar (met de aller-aller-aller beste compressie die er maar is). Mijn random generator doet het iets beter dan de standaard Java (2%). Echter mijn random generator heeft er 50% minder tijd voor nodig om 200000000 integer getallen te produceren.

Het enige probleem wat ik heb is met decimalen. Ik heb een long random getal, die ik makkelijk in een integer kwijt kan, maar zodra ik decimalen eraan hang, dan kloppen de verhoudingen niet meer. De enige oplossing die ik momenteel zie is om de standaard java random te gebruiken voor de decimalen. Nou ja, ik heb eigenlijk nog een paar andere mogelijkheden, maar dat vertraagd alleen maar. Ik zou wel eens willen weten hoe snel Cuda is.

Ik zal binnenkort de source posten, het is ondertussen 223 regels code om het visueel te maken. Dus maak je borst(en) maar nat.

Groetjes, Dippo

Gebruikersavatar
Berichten: 5.679

Re: Random nummer generator

Ik heb de 7zip test gedaan, maar ik twijfel weer. Ik heb gedaan wat 317070 zei, maar met 255 byte getallen is met mijn random generator en die van standaard Java, is de compressie 0%!
Dat wil zeggen dat de file niet kleiner kan worden gemaakt met compressie, wat een goede eigenschap is voor een random nummer generator (RNG).
Bij 64 byte getallen komen er tenminste wel een compressie naar voren in winrar
Wat bedoel je met 64 byte getallen?
Het enige probleem wat ik heb is met decimalen. Ik heb een long random getal, die ik makkelijk in een integer kwijt kan, maar zodra ik decimalen eraan hang, dan kloppen de verhoudingen niet meer.
Je bedoelt het weergeven van je random getallen in decimale vorm? Dat heeft niks met de opslag te maken, dus ik weet niet helemaal waar je dat in deze context voor gebruikt?

Een RNG genereert doorgaans random getallen van n bits (bijvoorbeeld n=32 of 64). Een typische manier om daarmee decimalen (0 t/m 9) te genereren is om simpelweg zo'n random 32-bit getal modulo 10 te nemen. Of als je het heel exact wilt doen: random getal modulo 10 indien het kleiner dan 4294967290 was, en anders opnieuw, anders hebben de decimalen 0 t/m 6 een héél klein miniscuul kansverschilletje.

Of in het algemeen, om random getallen tussen de 0 en k te verkrijgen (k exclusief) neem je een random getal modulo k als het kleiner was dan
\(k\lfloor 2^{32}/k\rfloor\)
en anders opnieuw.
Ik zou wel eens willen weten hoe snel Cuda is.
In potentie erg snel. Maar daar is het nodige getweak mee gemoeid, en je moet wel een hele bijzondere situatie hebben, wil je er werkelijk enig praktisch voordeel uit halen om je RNG in Cuda te schrijven.
In theory, there's no difference between theory and practice. In practice, there is.

Gebruikersavatar
Berichten: 5.609

Re: Random nummer generator

Ik heb de 7zip test gedaan, maar ik twijfel weer. Ik heb gedaan wat 317070 zei, maar met 255 byte getallen is met mijn random generator en die van standaard Java, is de compressie 0%!
Dat is schitterend. Als je daarmee bedoelt dat je bestand vooraf 100kB groot is, en achteraf ook 100kB, dan heb je een (heel) goede randomgenerator gemaakt. Proficiat ;)

Dat van die Cuda lijkt me ook sterk, dat hangt natuurlijk heel erg af van je algoritme, maar ik kan me geen randomgenerator voorstellen die veel baat heeft bij parallellisme of vectoroperaties... Veel winst ga je volgens mij dus niet maken.
What it all comes down to, is that I haven't got it all figured out just yet

And I've got one hand in my pocket and the other one is giving the peace sign

-Alanis Morisette-

Berichten: 8

Re: Random nummer generator

Goedenavond,

Rogier, wat ik bedoelde met 64 byte getallen, is dat ik een integer getal heb genomen tussen 0 en 64. De compressie met Rar ging toen wel goed.

Sorry, ik was niet duidelijk m.b.t. decimalen. Ik bedoelde eigenlijk float. Ik heb nu iets gevonden, ik denk dat ik het werkend heb kunnen krijgen in Java, maar ik durf het niet met zekerheid te zeggen. Daarnaast moet ik ook nog alle tests opnieuw doen vanwege de float aanpassing.

<knip>

Absolute Value of a Float

IEEE floating point uses an explicit sign bit, so the absolute value can be taken by a bitwise AND with the complement of the sign bit. For IA32 32-bit, the sign bit is an int value of 0x80000000, for IA32 64-bit, the sign bit is the long long int value 0x8000000000000000. Of course, if you prefer to use just int values, the IA32 64-bit sign bit is 0x80000000 at an int address offset of +1. For example:

double x;

/* make x = abs(x) */

*(((int *) &x) + 1) &= 0x7fffffff;

</plak>

Het is me niet gelukt om direct van long naar float te gaan, ik heb nu van long --> int --> float. Voordeel is wel, de abs kan er dan tussenuit. Vraag me niet waarom. Om dan toch maar verder te gaan over negatief, valt er profijt te halen uit negatieve getallen? Bijvoorbeeld dat een computer minder tijd nodig heeft om negatieve getallen te delen t.o.v. positieve getallen?

De reden waarom ik dit vraag, is vanwege dit plaatje:
test2.jpg
test2.jpg (475.75 KiB) 899 keer bekeken
Het enige wat verschilt is dat de kleur van een pixel (rgb) negatief kan zijn, voor de rest is de plaatsing van de pixel random. Echter blijft het raster op dezelfde plek. Wel mooi om te zien, het is net een animatie.

Ik heb een aantal fraaie plaatjes kunnen maken om tests uit te voeren:
screen_0022.jpg
screen_0022.jpg (397.4 KiB) 897 keer bekeken
Dit is een hoogte map, met het scherm als speelveld, iedere pixel die raak is krijgt een waarde verhoging van 1. De eerste pixel die een waarde van 32 bereikt is de winnaar. Daarna word de top 2% gemarkeerd en zal een tekst erbij gezet worden met het aantal graden en de x,y locatie. Het valt me wel op dat er af-en-toe een patroon in te vinden is, echter een regelmaat weer niet.

Ik zal binnenkort de source uploaden.

Groet, Dippo

Reageer