[C++] srand geeft geen random getallen terug

[Intrepidity]

Ik ben net begonnen met het leren van C++, vandaar deze wat simpele vraag.
Ik heb de volgende code om een willekeurig getal tussen de 1 en 100 af te drukken:

C++:

#include <iostream>
#include <cstdlib>
using namespace std;

int main()
{
    int random = 0;
    
    srand( time(NULL) );
    random = rand()%100+1;
    
    cout << "Willekeurig getal: " << random;
    
    return 0;
} 

Ik heb dus srand gebruikt met de tijd om random getallen te krijgen (normaal gesproken). Dat doet hij dus niet.. Ik krijg wel getallen tussen de 1 en 100, maar deze lopen zegmaar op..
Als ik bijvoorbeeld 56 terugkrijg en ik start het programma opnieuw, dan krijg ik 59, daarna 65, 78, enzovoort, het loopt alleen maar op tot de 100 en dan begint het weer bij 0..
Ik gebruik Dev-C++ als IDE en compiler. Wat doe ik fout?

[ Voor 4% gewijzigd door Intrepidity op 07-09-2005 10:40 ]

[Infinitive]

Kijk eens goed naar regel 10, daar staat de reden waarom je alleen random getallen tussen 1-100 krijgt.

[Intrepidity]

Infinitive schreef op woensdag 07 september 2005 @ 10:42:
Kijk eens goed naar regel 10, daar staat de reden waarom je alleen random getallen tussen 1-100 krijgt.

Dat is het probleem helemaal niet, het probleem is dat de getallen helemaal niet random zijn! ik wil juist dat ze tussen 1 en 100 blijven, maar zoals gezegd lopen de getallen alleen maar op, en krijg ik dus geen echt random getal terug..

[ Voor 13% gewijzigd door Intrepidity op 07-09-2005 10:44 ]

[Creepy]

Uit de rand manpage

"If you want to generate a random integer between 1
and 10, you should always do it by

j=1+(int) (10.0*rand()/(RAND_MAX+1.0));

Overigens, als je je programma bijv. elke seconde opstart dan zal het nooit echt random lijken aangezien je nu voor elk random nummer de seed initialiseert met de tijd.

[ Voor 31% gewijzigd door Creepy op 07-09-2005 10:54 ]

[Infinitive]

Ok, ik denk dat ik je nu begrijpt. Je start je programma een aantal keer en je komt erachter dat de getallen oplopend. Niet echt random dus, maar toch wel een beetje als ik die serie getallen van je ziet.

Ik verwacht dat het volgende het geval is: je trekt maar 1 random getal per programma uitvoering. Aan het begin van elke programma uitvoering zet je de seed aan de hand van de lokale tijd. Maar de seed bepaald de reeks random getallen die uit rand() komt. Maar daar pak je dus elke keer maar de eerste van, en die wordt dus eigenlijk direct door de seed bepaald (afhankelijk van de implementatie, bijv. nog een vermenigvuldiging en een modulo operatie op een groot getal, maar dat betekent dat als er oorsponkelijk een bepaalde ordening was (tijd), dat deze gedeeltelijk ook in het resultaat terug komt, afhankelijk van de modulo) en die was afhankelijk van de tijd. Van daar dat je niet echt goede random getallen krijgt.

edit:
@Creepy: maar dat lost zijn probleem nog niet op. Óf hij moet met zijn programma meer random getallen per keer trekken, of hij moet op een of andere manier de toestand van de random functie kunnen opslaan en herstellen bij de volgende programma executie.

[ Voor 31% gewijzigd door Infinitive op 07-09-2005 10:59 ]

[Creepy]

Infinitive schreef op woensdag 07 september 2005 @ 10:55:

edit:
@Creepy: maar dat lost zijn probleem nog niet op. Óf hij moet met zijn programma meer random getallen per keer trekken, of hij moet op een of andere manier de toestand van de random functie kunnen opslaan en herstellen bij de volgende programma executie.

Dat zeg ik toch?

[Intrepidity]

Kijk het is nu nog niet echt belangrijk voor me dat die getallen compleet random zijn, het is maar een simpele oefening, maar kan in een normale situatie met een wat complexer programma deze manier goed werken of is het gewoon beter dat ik meteen de manier van Creepy aanleer zegmaar?

[.oisyn]

Creepy schreef op woensdag 07 september 2005 @ 10:50:
Uit de rand manpage

---

"If you want to generate a random integer between 1
and 10, you should always do it by

j=1+(int) (10.0*rand()/(RAND_MAX+1.0));

---

Wat een onzin, waarom zou een modulo niet net zo goed zijn (of net zo slecht eigenlijk, je hebt in beide gevallen dat bepaalde resultaten 1x meer voor zullen komen dan de rest, uitgaande van een uniforme verdeling van rand())

[Verwijderd]

Komt mede door je srand(time).
Je initialiseert het randomalgoritme met de tijd (dat wist je natuurlijk ook wel).

Zet eens een lus om je Rand + print heen, en laat de srand buiten de lus. Dan druk je een aantal getallen af waaraan je ziet dat je een redelijk random reeks hebt.


Als je echt bij het opstarten van je prog één keer een random waarde gaat trekken, kun je eventueel zoiets doen:

srand(time)
srand(rand()*MAX_RAND);
srand(rand()*MAX_RAND);
srand(rand()*MAX_RAND);


of zoiets:

srand(time)
// nu een random aantal keer (maar minstens 5x) het startpunt van de random reeks bepalen op basis van een random waarde:
for (int i=0; i< ((rand()*5) + 5 ; i++)
{
srand(rand()*MAX_RAND);
}


En eventueel roep je Srand aan met een waarde geXORred met een andere random waarde...
enzovoorts.

[ Voor 63% gewijzigd door Verwijderd op 07-09-2005 11:34 ]

[DrClaw]

Beste BartXP,

het hangt allemaal af van wat je uiteindelijke programma moet doen. Als je gewoon wat random nummers meot genereren, bijvoorbeeld voor een kaartspelletje ofzo, dan is srand en rand ruim voldoende. gewoon eenmaal initialiseren met srand, en dan tig keer rand aanroepen.

als je echter wilt, dat de random getallen nergens van afhankelijk zijn, ofwel dat de entropie zo groot mogelijk is, dan zul je je random getallen dus op een andere manier moeten genereren.

er zijn al verschillende uitvindingen gedaan om dus de seed en de random getallen zelf te laten afhangen van neit voorspelbare waarden, zoals seek time van je harddrive, of van het heen en weer rammelen van je muis, of van statische ruis in plaatjes, of zelfs van statische ruis in de lucht.

en om nu een beetje te spammen: er is zelfs een website waar je random nummers kunt downloaden: random.org. deze nummers worden doormiddel van atmosferische invloeden random bepaald, en er zijn zelfs programmeurs die dat in hun random functie hebben ingebakken (ze downloaden dan zo'n file met random nummers en lezen die 1 voor 1 uit).

maar ja, als het dus voor een random kleurtje op de achtergrond van je webpagina gaat ofzo, gebruik dan rand zou ik zeggen

[Haploid]

Als je telkens srand() blijft aanroepen, dan krijg je telkens het eerste getal uit een of andere reeks van pseudo-random getallen. Maar als je de eerste getallen uit al die reeksen naast elkaar plaatst, dan hoeft dat niet ook een pseudo-random reeks op te leveren. Ik weet niet precies welke berekening er in srand() precies wordt uitgevoerd, maar zoals je al opgemerkt hebt is het een enigzins deterministisch proces.

Voor een nette pseudo-random reeks roep je 1 keer srand() aan, en daarna niet meer. Moeilijk als je die reeks wilt behouden tussen programma-aanroepen. Je kunt ook iets anders gebruiken als seed; (time(NULL)^2)>>1 of zoiets geks.

edit:
Of wat mGerben zegt, ziet er ook pretty random uit.

[ Voor 6% gewijzigd door Haploid op 07-09-2005 11:41 ]

[Creepy]

.oisyn schreef op woensdag 07 september 2005 @ 11:24:
[...]


Wat een onzin, waarom zou een modulo niet net zo goed zijn (of net zo slecht eigenlijk, je hebt in beide gevallen dat bepaalde resultaten 1x meer voor zullen komen dan de rest, uitgaande van een uniforme verdeling van rand())

Ff een wat meer volledige quote:

In Numerical Recipes in C: The Art of Scientific Computing
(William H. Press, Brian P. Flannery, Saul A. Teukolsky,
William T. Vetterling; New York: Cambridge University
Press, 1990 (1st ed, p. 207)), the following comments are
made:
"If you want to generate a random integer between 1
and 10, you should always do it by

j=1+(int) (10.0*rand()/(RAND_MAX+1.0));

and never by anything resembling

j=1+((int) (1000000.0*rand()) % 10);

(which uses lower-order bits)."

Random-number generation is a complex topic. The Numeri­
cal Recipes in C book (see reference above) provides an
excellent discussion of practical random-number generation
issues in Chapter 7 (Random Numbers).
For a more theoretical discussion which also covers many
practical issues in depth, please see Chapter 3 (Random
Numbers) in Donald E. Knuth's The Art of Computer Program­
ming, volume 2 (Seminumerical Algorithms), 2nd ed.; Read­
ing, Massachusetts: Addison-Wesley Publishing Company,
1981.

Maar waarom het nu precies zo is weet ik ook niet aangezien ik dat boek niet gelezen heb, tis maar een dommy copy'n'paste actie

Overigens kan ik hier het effect van de puur oplopende nummers niet reproduceren. Het "lijkt" hier in elk geval random te zijn.

[ Voor 9% gewijzigd door Creepy op 07-09-2005 11:44 ]

[.oisyn]

Dat is al wat anders dan je hier zei, maar waarom je het met een modulo met 100000.0 zou willen vermenigvuldigen beats me eerlijk gezegd . Ze hebben gelijk dat je eigenlijk al je bits uit rand() zou moeten gebruiken om je waarde te bepalen, maar bij een conversion naar een float of double doe je dat ook niet

Stel je wilt een random boolean hebben, dan zou je zoiets doen:

C++:

bool value = (rand() / (RAND_MAX + 1.f)) >= 0.5f;

Zou goed moeten zijn volgens die quote, je gebruikt immers float. Maar je gebruikt echter niet alle bits, je gebruikt eigenlijk alleen maar de most significant bit die rand() returnt. Dat is natuurlijk net zo slecht als een modulo gebruiken:

C++:

bool value = (rand() % 1 == 0);

Want nu kijk je alleen maar naar de least significant bit.

Daarnaast, en dat is wat ik aanhaalde in deze thread, krijg je geen uniforme verdeling als de deling van RAND_MAX+1 door het aantal waarden dat je wilt hebben een rest heeft. Als je een loopje maakt van 0 tot RAND_MAX (en dat gebruikt als je random waarde), en je voert de berekeningen uit en je telt hoevaak elk resultaat voorkomt, dan zul je zien dat bepaalde resultaten 1 keer meer voorkomen dan andere. Of je nou rekent met floats of met ints; je originele input heeft al eindige precisie dus een conversion naar float maakt geen zak uit, itt wat sommige denken .

[.oisyn]

Verwijderd schreef op woensdag 07 september 2005 @ 11:28:
Als je echt bij het opstarten van je prog één keer een random waarde gaat trekken, kun je eventueel zoiets doen:

srand(time)
srand(rand()*MAX_RAND);
srand(rand()*MAX_RAND);
srand(rand()*MAX_RAND);

Pointless, als de eerste rand() van alle seeds geen uniforme random returnd hebben de rest van je acties ook niet echt nut. Wellicht is het minder duidelijk zichtbaar, maar het blijft natuurlijk gewoon een transformatie van de ene getallenrange naar de ander, en je verandert niets aan de entropie.

// nu een random aantal keer (maar minstens 5x) het startpunt van de random reeks bepalen op basis van een random waarde:
for (int i=0; i< ((rand()*5) + 5 ; i++)
{
srand(rand()*MAX_RAND);
}

Zelfde verhaal natuurlijk

En eventueel roep je Srand aan met een waarde geXORred met een andere random waarde...
enzovoorts.

dito

Haploid schreef op woensdag 07 september 2005 @ 11:40:
(time(NULL)^2)>>1 of zoiets geks.

Als time al niet random was is een constante bewerking op die time natuurlijk ook niet random . Je verandert nu alleen maar de seed die je aanroept, maar zoals gezegd gebruik je steeds een nieuwe seed bij elke startup, en een nieuwe seed voor elke random is gewoon niet goed, wat voor seed je ook zet.

[ Voor 20% gewijzigd door .oisyn op 07-09-2005 11:58 ]

[Intrepidity]

Erg bedankt, met de bovenstaande maniertjes is het al een stuk random'er

Creepy schreef op woensdag 07 september 2005 @ 11:40:
Overigens kan ik hier het effect van de puur oplopende nummers niet reproduceren. Het "lijkt" hier in elk geval random te zijn.

Kan het misschien aan de compiler liggen die ik gebruik? ik heb een dergelijke code ook wel eens in VS .NET voorbij zien komen, en volgensmij werkte het daar wel volledig random..

[Creepy]

Ligt niet aan de compiler, maar aan de standard libs die je gebruikt. Ik heb geen idee hoe de implementatie van rand() er in DevCPP uit ziet maar die zou best wel eens anders kunnen zijn dan die van GCC (waarmee ik ff snel heb getest) en die van VS.

[Haploid]

.oisyn schreef op woensdag 07 september 2005 @ 11:55:
[...]
Als time al niet random was is een constante bewerking op die time natuurlijk ook niet random . Je verandert nu alleen maar de seed die je aanroept, maar zoals gezegd gebruik je steeds een nieuwe seed bij elke startup, en een nieuwe seed voor elke random is gewoon niet goed, wat voor seed je ook zet.

Je hebt natuurlijk helemaal gelijk. Het was alleen bedoeld om het verband tussen de niet-zo-random getallen wat te verdoezelen, net als mGerben's methode. De enige echt nette methode is als je maar 1 keer seed en dan vervolgens rand() blijft gebruiken. Als dat voor hem een mogelijkheid is.

[RickN]

.oisyn schreef op woensdag 07 september 2005 @ 11:24:
[...]


Wat een onzin, waarom zou een modulo niet net zo goed zijn (of net zo slecht eigenlijk, je hebt in beide gevallen dat bepaalde resultaten 1x meer voor zullen komen dan de rest, uitgaande van een uniforme verdeling van rand())

Het is geen onzin hoor. Dat bepaalde waarden minimaal één keer vaker zullen voorkomen dan andere (soort van pigeonhole principle eigenlijk) is een feit en heeft er niks mee te maken.

Bij de minst significante bits weet je b.v. ook nog precies welke waarden dat zullen zijn (namelijk 0 tm (RAND_MAX % n)). Bij de meest significante bits daarentegen zullen bepaalde waarden wel vaker voorkomen, maar welke dat zijn is min of meer random.

De randomness van dit soort pseudo-random getallen wordt doorgaans "gemeten" met een aantal statistische tests (b.v. run-length, chi-square). Het is met deze tests eenvoudig aan te tonen dat de minst significate bits van een eenvoudige additive congruential random number generator (wat random() is) van mindere kwaliteit zijn dan de meest significate bits. Overigens tonen veel van die tests ook aan dat de kwaliteit van random() überhaupt eigenlijk vrij belabbert is, ongeacht welke bit je neemt.

[ Voor 37% gewijzigd door RickN op 07-09-2005 15:11 ]

[MSalters]

RickN schreef op woensdag 07 september 2005 @ 15:10:
[...]
Het is geen onzin hoor. Dat bepaalde waarden minimaal één keer vaker zullen voorkomen dan andere (soort van pigeonhole principle eigenlijk) is een feit en heeft er niks mee te maken.

Hoezo? Het meest simpele algoritme dat aantoonbaar niet biased is:

C++:

int random;
while ( (random=srand( )) >= max );

Het kan uiteraard efficienter.

Bij de minst significante bits weet je b.v. ook nog precies welke waarden dat zullen zijn (namelijk 0 tm (RAND_MAX % n)). Bij de meest significante bits daarentegen zullen bepaalde waarden wel vaker voorkomen, maar welke dat zijn is min of meer random.

Het is marginaal meer random.

Overigens tonen veel ... tests ook aan dat de kwaliteit van random() überhaupt eigenlijk vrij belabbert is, ongeacht welke bit je neemt.

Misschien bij een el-cheapo game-oriented rand( ) functie (typisch een LCG), maar het stikt van de fatsoenlijke RNG's. In C++0x komen waarschijnlijk de RNG's uit boost, en dat zijn statistich betere.

[Tomatoman]

In hoeverre gegenereerde getallen werkelijk random zijn is misschien van belang in wetenschappelijke applicaties, maar in de meeste huis-tuin-en-keukentoepassingen voldoen de standaard functies om random getallen te genereren prima.

[Zoijar]

Blitz++ heeft ook wat random number generators etc.