[C] random getallen

[Marc]

ik ben even iets aan het maken en daarvoor heb ik random getallen nodig, waarvan ik de limiet kan instellen. bv een random getal tussen de 0-10.
nu heb ik van iemand gehoord dat dit kan met
rand() % 11;

en dit werkte inderdaad, maar na een poosje kwam ik er achter dat die getallen helemaal niet random waren, ik geef een voorbeeld:

code:

#include <stdio.h>

main()
{
   int i = rand() % 11;

   printf("%d\n", i);

   return 0;
}

nu testte ik het een paar keer:

code:

[sanchez@vncs coding]$ ./test
6
[sanchez@vncs coding]$ ./test
6[sanchez@vncs coding]$ ./test
6
[sanchez@vncs coding]$ ./test
6

tsja dit is niet echt wat ik onder random versta...heeft iemand mischien een beter idee?

[D2k]

seed
[edit]
[topic=137788/1/25]

[Marc]

ja das voor C++, de functie randomize() kent C niet geloof ik.

[roelio]

ANSI C stdlib:
seed instellen met srand(getal)
random getal met rand()

[Marc]

ah mooi het werkt

tnx

[roelio]

volgende keer ff google-en met "c reference random integer" ofzo ???

[RickN]

Ik zou zowiezo ff doorzoeken naar wat documentatie, want ik meen me te herinneren dat ik in de man-page van rand ooit heb gelezen dat mod n niet zo'n goeie methode is om getallen tussen 0 en n te krijgen.

[Verwijderd]

Op zondag 24 februari 2002 23:30 schreef RickN het volgende:
Ik zou zowiezo ff doorzoeken naar wat documentatie, want ik meen me te herinneren dat ik in de man-page van rand ooit heb gelezen dat mod n niet zo'n goeie methode is om getallen tussen 0 en n te krijgen.

Waarom quote je dan niet gelijk ff, manpages quoten mag

code:

     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, 1992 (2nd ed., p. 277)), the following comments are
     made:
          "If you want to generate a random integer between 1
          and 10, you should always do it by using high-order
          bits, as in

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

          and never by anything resembling

               j=1+(rand() % 10);

          (which uses lower-order bits)."

[RickN]

Op zondag 24 februari 2002 23:39 schreef mietje het volgende:

[..]

Waarom quote je dan niet gelijk ff, manpages quoten mag

Waarom zou ik, ik hoef het toch niet te weten

Maar dit bedoelde ik dus. De reden is me een beetje onduidelijk, kan iemand daar wat meer over vertellen?

[Soultaker]

Op maandag 25 februari 2002 10:05 schreef RickN het volgende:
Maar dit bedoelde ik dus. De reden is me een beetje onduidelijk, kan iemand daar wat meer over vertellen?

Het is vrij logisch. Stel dat je random generator getallen genereert tussen de 0 en de 123. Dat is een gek getal, maar het is maar om 't voorbeeld. Als je dan een getal tussen de 0 en 99 genereert door middel van (rand()%100) (waarbij je dus in feite de laatste twee decimalen van rand() neemt), is de kans dat een getal onder of gelijk aan 23 gekozen wordt twee keer zo groot als een getal boven de 23. Om 20 te genereren moet rand() immers 20 OF 120 genereren, voor 50 voldoet alleen 50.

In de praktijk ligt het maximumbereik meestal op 2^31, waardoor dit effect een stuk geringer is, maar het is nog steeds aanwezig. Als je een echt uniforme verdeling wilt, zul je het dus anders moeten doen.

Door gebruik te maken van floating point getallen (zoals in de manual page voorgedaan wordt) kun je het bereik van de random functie (bijna) netjes in even grote gebieden opdelen en zal elk getal na een groot aantal generaties bij benadering even vaak voorkomen.

[Killemov]

Tjonge, op de Amiga heb ik nog een randomizer gemaakt op basis van de systeemklok en wat andere hardware registers. Op een Wintel heb ik dat echter nog nooit geprobeerd. Heeft iemand daar ervaring mee?

[Soultaker]

Op maandag 25 februari 2002 15:58 schreef Killemov het volgende:
Tjonge, op de Amiga heb ik nog een randomizer gemaakt op basis van de systeemklok en wat andere hardware registers. Op een Wintel heb ik dat echter nog nooit geprobeerd.

Dat lijkt me een nogal slechte oplossing. Als je nu een lusje maakt, is er een grote kans dat in een iteratie de systeemklok en de registers hetzelfde zijn als de vorige keer, waardoor je dus hetzelfde getal genereerd.

Je zal waarschijnlijk altijd een pseudo-random nummergenerator willen hebben, die je dan seed met (bijvoorbeeld) de systeemklok of een combinatie van interne systeemwaardes.

[.oisyn]

Op maandag 25 februari 2002 12:53 schreef Soultaker het volgende:

[..]

Het is vrij logisch. Stel dat je random generator getallen genereert tussen de 0 en de 123. Dat is een gek getal, maar het is maar om 't voorbeeld. Als je dan een getal tussen de 0 en 99 genereert door middel van (rand()%100) (waarbij je dus in feite de laatste twee decimalen van rand() neemt), is de kans dat een getal onder of gelijk aan 23 gekozen wordt twee keer zo groot als een getal boven de 23. Om 20 te genereren moet rand() immers 20 OF 120 genereren, voor 50 voldoet alleen 50.

In de praktijk ligt het maximumbereik meestal op 2^31, waardoor dit effect een stuk geringer is, maar het is nog steeds aanwezig. Als je een echt uniforme verdeling wilt, zul je het dus anders moeten doen.

ik denk niet dat dit de reden is dat je floats moet gebruiken... Want zoals je al zei, stel dat je rand () in de practijk een waarde oplevert tussen 0 en 2³¹, en je wilt een waarde van 0 t/m 99, dus je pakt rand () % 100

2³¹ = 2147483648, dus rand () geeft een waarde tussen 0 en 2147483647 (inclusief)

de kans voor een getal onder de 48 is 21474837 / 2147483648 = 0.01000000024214387
de kans voor 48 of hoger is 21474836 / 2147483648 = 0.009999999776482582

dat verschil is minimaal dus

Ik denk meer dat het te maken heeft met het feit dat rand () zijn getallen genereert door steeds te vermenigvuldigen met een (heel groot) priemgetal. Ik denk dat door steeds te kijken naar het onderste gedeelte van het grote getal lijkt er veel meer herhaling op te treden, dan wanneer je de volledige uitkomst meeneemt en dat terugbrengt naar een getal tussen de grenzen die je wilt hebben

[RickN]

Op maandag 25 februari 2002 19:53 schreef OiSyN het volgende:

[..]

ik denk niet dat dit de reden is dat je floats moet gebruiken... Want zoals je al zei, stel dat je rand () in de practijk een waarde oplevert tussen 0 en 2³¹, en je wilt een waarde van 0 t/m 99, dus je pakt rand () % 100

2³¹ = 2147483648, dus rand () geeft een waarde tussen 0 en 2147483647 (inclusief)

de kans voor een getal onder de 48 is 21474837 / 2147483648 = 0.01000000024214387
de kans voor 48 of hoger is 21474836 / 2147483648 = 0.009999999776482582

dat verschil is minimaal dus

Ik denk meer dat het te maken heeft met het feit dat rand () zijn getallen genereert door steeds te vermenigvuldigen met een (heel groot) priemgetal. Ik denk dat door steeds te kijken naar het onderste gedeelte van het grote getal lijkt er veel meer herhaling op te treden, dan wanneer je de volledige uitkomst meeneemt en dat terugbrengt naar een getal tussen de grenzen die je wilt hebben

Dat verschil is wel klein, maar niet verwaarloosbaar hoor. In b.v. Montecarlo simulaties moet je miljarden random getallen genereren en zo'n afwijking in de 'randomness' is daar zeker wel een ernstige zaak en kan de hele simulatie waardeloos maken. Ik hou het persoonlijk dus toch op Soultakers uitleg.

[.oisyn]

Op maandag 25 februari 2002 20:52 schreef RickN het volgende:

[..]

Dat verschil is wel klein, maar niet verwaarloosbaar hoor. In b.v. Montecarlo simulaties moet je miljarden random getallen genereren en zo'n afwijking in de 'randomness' is daar zeker wel een ernstige zaak en kan de hele simulatie waardeloos maken. Ik hou het persoonlijk dus toch op Soultakers uitleg.

uhm, als je zulk soort berekeningen moet doen dan moet je sowieso al een andere implementatie van een random number generator gebruiken dan diegene die standaard aanwezig is, want die voldoet bij lange na niet aan de eisen die worden gesteld bij simulaties

[RickN]

Op maandag 25 februari 2002 22:29 schreef OiSyN het volgende:

[..]

uhm, als je zulk soort berekeningen moet doen dan moet je sowieso al een andere implementatie van een random number generator gebruiken dan diegene die standaard aanwezig is, want die voldoet bij lange na niet aan de eisen die worden gesteld bij simulaties

Jawel hoor, de meest gebruikelijke implementatie voor een rand() achtige functie is m.b.v. een linear congruential generator.

Dit is een iteratieve functie die er alsvolgt uitziet:

N_i+1 = (a · N_i + c) mod m

edit:
in de betere implementaties worden nog allerlei shuffle operaties op de uitvoer losgelaten

Het is zeker mogelijk om met deze methode een verschrikkelijk slechte random generator te implementeren (en dat is in het verleden ook gebeurd), maar bij een goede keuze voor de parameters, is dit een uitstekende manier om een sequence pseudorandom getallen te genereren die aan alle eisen voldoet die je maar kunt bedenken.

De C standaard schrijft geen specifieke methode voor bij het implementeren van de rand() functie, maar ze adviseren als methode een linear congruential generator. Ik ben er vrijwel van overtuigt dat de versie van rand() die in de standaard bibliotheken van b.v. Linux wordt meegeleverd van dusdanige kwaliteit is dat die voor elke toepassing die een pseudorandom sequence vereist geschikt is.

edit:
Anders zal er zeker een alternatieve random functie zijn (die dan waarschijnlijk iets langzamer is) die helemaal geweldig is

[.oisyn]

Op maandag 25 februari 2002 22:51 schreef RickN het volgende:
[.. knip ..]

Ik ben er vrijwel van overtuigt dat de versie van rand() die in de standaard bibliotheken van b.v. Linux wordt meegeleverd van dusdanige kwaliteit is dat die voor elke toepassing die een pseudorandom sequence vereist geschikt is.

veel programmeurs schijnen daar anders over te denken...

ik heb even zitten zoeken naar de source van de rand () functie in een willekeurige linux distributie, maar jammer genoeg niets kunnen vinden (en ik heb hier geen linux)... maar dit heb ik uit djgpp gevist (die gebaseerd is op gnu's libc):

code:

/* Copyright (C) 1994, 1996, 1998, 1999 DJ Delorie */
static unsigned long long next = 1;

int rand(void)
{
    /* This multiplier was obtained from Knuth, D.E., "The Art of
    Computer Programming," Vol 2, Seminumerical Algorithms, Third
    Edition, Addison-Wesley, 1998, p. 106 (line 26) & p. 108 */

    next = next * 6364136223846793005LL + 1;
    /* was: next = next * 0x5deece66dLL + 11; */
    return (int)((next >> 21) & DJ_RAND_MAX);
}

void srand(unsigned seed)
{
    next = seed;
}

edit:
Anders zal er zeker een alternatieve random functie zijn (die dan waarschijnlijk iets langzamer is) die helemaal geweldig is

juist, daar doelde ik dus ook op