[c++] Random discusie

[Vulpecula]

Op school hadden we vandaag programmeren. Nu moesten we een programma maken dat je gebruiker een getal ingedachte neemt en de computer moet het raden.

Dus de computer moet een random getal kiezen. En de gebruiker moet dan aangeven door bijv. L=lager, H=hoger of C=correct intevullen.

Stel je voor.
Je neemt het getal 50 ingedachte, het eerste random getal dat de pc geeft is bijv. 30.
Nu hoeft de pc geen random meer uittevoeren tussen 0 en de 30. Hoe kun je ervoor zorgen dat hij vanaf de 30 tot de 100 een random getal kiest?

[Verwijderd]

Bovenin het menu'tje van dit forum zie je een blauwe balk met daarop onder andere een knop 'search'. Als je even een search doet op de keywords "random c++" heb je zo wat te pakken.

Greetz

edit:
Sjeez, 214 posts al, je had eigenlijk moeten weten dat je dit soort dingen eerst ff moet proberen te vinden met de search..

[Verwijderd]

Random lijkt me niet zo handig? binary search lijkt me vele male effectiver..

[Vulpecula]

Ik heb de search allang gebruikt maar er stond nix bruikbaars in.

[Ericston]

srand() en rand()

--------edit--------

En dit...

If you want to generate a random integer between 1 and 10, you should always do it by using high-order bits, as in

code:

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

and never by anything resembling

code:

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

(which uses lower-order bits).

...vond ik in een (1) van de hits.

[Verwijderd]

Mensen hoe random werkt weet ie al want hij heeft immers die 1e gok van 30 er er ook uit gekregen (lezen is ook een vak)

Random tussen 30 en 100 is natuurlijk een random tussen 0 en 70 en daar 30 bij optellen (zo ingewikkeld is het toch niet)

ps. Toch blijf ik er bij dat een binary search effectiver is.

[Janoz]

Zoek op google anders eens naar binary search of kijk in hoofdstuk 1.1 van "Efficient zoeken voor dummies" .. Het ID:

vraag 50
als hoger dan vraag 75
als lager dan vraag 25
enz enz enz.. Gegarandeerd dat je het antwoord binnen ² log 100 stappen hebt.

[ps] ga dit niet helemaal uitschrijven.. Er zijn heel makkelijke algoritmes te bedenken die het midden tussen een onder en bovengrens bepalen.

[Ericston]

Op maandag 10 september 2001 17:40 schreef Yarvieh het volgende:
(lezen is ook een vak)

Yup.

[.oisyn]

toen ik de topictitel las dacht ik: heej, een random (oftewel: een willekeurige) discussie over C++, lache, even kijken wat daar te discussieren valt. Maar toen ik keek ging het over 'random'

[Janoz]

Op maandag 10 september 2001 18:55 schreef OiSyN het volgende:
toen ik de topictitel las dacht ik: heej, een random (oftewel: een willekeurige) discussie over C++, lache, even kijken wat daar te discussieren valt. Maar toen ik keek ging het over 'random'

Zelfs een discussie over random is intresant (hou random is random op een pc ed).. Maar ja, dat zit er zelfs niet in

[Verwijderd]

Misschien kunnen we wat random generators schrijven en die benchmarken?

[.oisyn]

Op maandag 10 september 2001 19:08 schreef Janoz het volgende:

[..]

Zelfs een discussie over random is intresant (hou random is random op een pc ed).. Maar ja, dat zit er zelfs niet in

Ik geloof niet in random, en er is NIETS ter wereld hoe je ook maar een volledig random getal kunt bepalen

[Infinitive]

toen ik de topictitel las dacht ik: heej, een random (oftewel: een willekeurige) discussie over C++, lache, even kijken wat daar te discussieren valt. Maar \ldots

Dat kan natuurlijk nog verandert worden Waar wil je het over hebben

[Verwijderd]

Op maandag 10 september 2001 19:11 schreef Yarvieh het volgende:
Misschien kunnen we wat random generators schrijven en die benchmarken?

/me is in

[marcusk]

Op maandag 10 september 2001 19:18 schreef OiSyN het volgende:
Ik geloof niet in random, en er is NIETS ter wereld hoe je ook maar een volledig random getal kunt bepalen

Oh? Het verval van kerndeeltjes bijvoorbeeld is toch echt volledig willekeurig.

[TlighT]

Op maandag 10 september 2001 20:50 schreef marcusk het volgende:

[..]

Oh? Het verval van kerndeeltjes bijvoorbeeld is toch echt volledig willekeurig.

Vertel dat maar aan Einstein...

[GiLuX]

gewoon maar een observatie:

iemand start deze topic met een vraag over C++,
hij wordt vervolgens direct afgezeken omdat hij de search niet had gebruikt volgens een alwetend persoon die C++ als sig heeft en dus al veelsteveel weet om met dit soort simpele materie geconfronteerd te worden maar nog veel meer verstand heeft van search buttons,
vervolgens gaan andere forum users het over radioactief verval hebben of hun eigengemaakte smilies ten toonstellen.

[Verwijderd]

Iets beter observeren dan, ik heb z'n vraag m.i. perfect beantwoord,en dat we daarna een beetje offtopic raken, who carez?!

[GiLuX]

nothing personal,
ik zat dit te lezen en dacht dit gaat nergens over.

thats all

[.oisyn]

Op maandag 10 september 2001 23:04 schreef GiLuX het volgende:
gewoon maar een observatie:

iemand start deze topic met een vraag over C++,
hij wordt vervolgens direct afgezeken omdat hij de search niet had gebruikt volgens een alwetend persoon die C++ als sig heeft en dus al veelsteveel weet om met dit soort simpele materie geconfronteerd te worden maar nog veel meer verstand heeft van search buttons,
vervolgens gaan andere forum users het over radioactief verval hebben of hun eigengemaakte smilies ten toonstellen.

Zie je sneech, het ligt dus niet aan mij

Anyway, voor de rest klopt jouw observatie ook niet helemaal, GiLuX

[Verwijderd]

Hey

Laat ik nu net een random generator (in C++) geimplementeerd hebben Werkt volgens het Mersenne-Twister principe, genereert 32-bits random getallen, en is +- 4x zo snel als rand() (die maar 15 bits genereert).

Wie biedt meer?

[.oisyn]

ik gebruik diegene die bij djgpp zat altijd (want ik heb een hekel aan de implementatie van m$ met zijn 15 bits )

die is 32 bits, maar gebruikt een 64 bits seed die steeds wordt vermenigvuldigd

[GiLuX]

achja,
weetje,
ik zag die reply van sneech en vervolgens rest van de topic die nergens meer heen ging en toen moest ik opeens aan die arme topic starter denken die nu huilend in zijn bedje ligt met een uzi onder zijn kussens omdattie niet serieus word genomen en nu morgen zijn opdrachtje niet af heeft en daarom morgen zijn hele school overhoopt schiet omdattie te veel quake heeft gespeeld ipv het ontdekken van de search button.

enniewee,
iedereen schijnt zich aangesproken te voelen,
sorry, ik heb een beetje last van gdiep

[.oisyn]

code:

#define DJ_RAND_MAX 0x7fffffff

static unsigned __int64 next = 1;

int dj_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 * 6364136223846793005L + 1;
    /* was: next = next * 0x5deece66dLL + 11; */
    return (int)((next >> 21) & DJ_RAND_MAX);
}

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

[Verwijderd]

Op maandag 10 september 2001 23:37 schreef OiSyN het volgende:
ik gebruik diegene die bij djgpp zat altijd (want ik heb een hekel aan de implementatie van m$ met zijn 15 bits )

die is 32 bits, maar gebruikt een 64 bits seed die steeds wordt vermenigvuldigd

Ow, maar dat is een simpele generator ala Knuth. Die zijn inderdaad retesnel, maar de periode is erg klein, dus na een paar duizend getallen worden ze cyclisch (begint de reeks van voren af aan).

Zo'n Mersenne-Twister (en rand() ook), zijn hogere orde rng's, en daarbij duurt het veel langer voordat ze cyclisch worden (bij mijn implementatie duurt het gemiddeld 1,5 miljard getallen voor er een dubbel getal wordt gegenereerd, maar de periode ligt nog veel hoger).

<edit>
Te laat gepost

Overigens is de comment header van m'n files nog langer dan jouw implementatie, ik gebruik iets dergelijks om de seed (623 unsigneds lang) te genereren
</edit>

[Verwijderd]

Op maandag 10 september 2001 23:37 schreef GiLuX het volgende:
enniewee,
iedereen schijnt zich aangesproken te voelen,
sorry, ik heb een beetje last van gdiep

Volgens mij voelt niemand zich persoonlijk aangesproken, jij meld dat we de topic starter niet geholpen hebben en alleen maar offtopic zitten te blaten,dat is gewoon niet waar dus daar krijg je reacties op, logish toch?

[.oisyn]

Op maandag 10 september 2001 23:52 schreef Yarvieh het volgende:

[..]

Volgens mij voelt niemand zich persoonlijk aangesproken, jij meld dat we de topic starter niet geholpen hebben en alleen maar offtopic zitten te blaten,dat is gewoon niet waar dus daar krijg je reacties op, logish toch?

laat die jonge nou toch, hij heeft griep

[.oisyn]

Op maandag 10 september 2001 23:51 schreef mietje het volgende:

[..]

Ow, maar dat is een simpele generator ala Knuth. Die zijn inderdaad retesnel, maar de periode is erg klein, dus na een paar duizend getallen worden ze cyclisch (begint de reeks van voren af aan).

Nou, de cycle is wel wat langer dan een paar duizend hoor. Misschien niet superlang, maar hij voldoet gigantisch goed

[curry684]

Op maandag 10 september 2001 17:24 schreef frankschers het volgende:
Op school hadden we vandaag programmeren. Nu moesten we een programma maken dat je gebruiker een getal ingedachte neemt en de computer moet het raden.

Dus de computer moet een random getal kiezen. En de gebruiker moet dan aangeven door bijv. L=lager, H=hoger of C=correct intevullen.

Stel je voor.
Je neemt het getal 50 ingedachte, het eerste random getal dat de pc geeft is bijv. 30.
Nu hoeft de pc geen random meer uittevoeren tussen 0 en de 30. Hoe kun je ervoor zorgen dat hij vanaf de 30 tot de 100 een random getal kiest?

Dit is algoritme-les, geen programmeerles. Het correcte hoger-lager algoritme is een van de eerste dingen die je hoort te leren inderdaad.

Als iemand irl hoger-lager met jou doet op een getal van 0-100 ga je toch ook steeds halverwege zitten, waarom de computer dan niet? Hier moet (lees MAG) je random helemaal niet bij gebruiken, lijkt me zelfs zware minpunten voor deze opdracht als de docent een beetje hersens heeft. Wordt iets in de richting van (sorry ik ben allergisch voor cin en cout en gebruik dus ook in C++ altijd printf):

code:

#include <stdio.h>
#include <conio.h>

#define LowerCase(p_Char) (((p_Char) >= 'A' && (p_Char) <= 'Z') ? (p_Char) - 32 : (p_Char))

const int c_MinGetal     = 0;
const int c_MaxGetal     = 100;

int main()
{
int  l_MinGetal  = c_MinGetal;
int  l_MaxGetal  = c_MaxGetal;
int  l_Pogingen  = 0;
int  l_Gok;
char    l_Input;

// Druk welkomstmededeling af
printf("Hoger-lager\n\nNeem een getal in gedachten tussen %d "
     "en %d. Druk op een toets daarna.", c_MinGetal, c_MaxGetal);
while(!getchar());

// Eindeloze loop totdat we gelijk hebben gekregen
while(true)
  {
  // Maak een nieuwe gok en verhoog aantal pogingen
  l_Gok = (l_MinGetal + l_MaxGetal) / 2;
  l_Pogingen++;

  // Druk gok af en wacht op een correct antwoord 
  printf("Ik gok %d.", l_Gok);
  do
    {
    printf("\nMoet ik (H)oger, (L)ager of is dit (C)orrect? ");
    l_Input    = LowerCase(getchar());
    }
  while(l_Input != 'h' && l_Input != 'l' && l_Input != 'c');

  // Handel het antwoord correct af
  if    (l_Input == 'c')
    break;
  else if (l_Input == 'h')
    l_MinGetal    = l_Gok;
  else if (l_Input == 'l')
    l_MaxGetal    = l_Gok;
  }

// Druk aantal pogingen af en wacht op input
printf("Ik had %d poging%s nodig!\n\n", l_Pogingen,
     l_Pogingen == 1 ? "" : "en");
printf("Druk op een toets om te beeindigen...");
while(!getchar());

// Verlaat programma zonder fouten
return 0;
}

As usual: Niet door de compiler geweest, en 100% not guaranteed to work

Je kunt met die consts bovenin spelen voor een grotere range, en volgens mij heb ik ieder bonuspunt hier voor je binnengehaald (tot aan het al of niet meervoud bij het aantal pogingen aan toe )

[Verwijderd]

Op dinsdag 11 september 2001 00:18 schreef OiSyN het volgende:
Nou, de cycle is wel wat langer dan een paar duizend hoor. Misschien niet superlang, maar hij voldoet gigantisch goed

Hmm, ik zit erover na te denken of hij ooit 31 0-bits zal returnen, maar het lijkt me wel. Die 64-bits waarde kan (mag) iig. nooit 0 worden. Je kunt de periode verlengen door bits te folden, dus iets als:
return (((int)(next >> 21)) ^ ((int)(next >> 30))) & DJ_RAND_MAX;

[.oisyn]

Op dinsdag 11 september 2001 01:42 schreef curry684 het volgende:

(sorry ik ben allergisch voor cin en cout en gebruik dus ook in C++ altijd printf)

aaaah een man naar mijn hart

printf & co. heerst

[.oisyn]

Op dinsdag 11 september 2001 02:03 schreef mietje het volgende:

[..]

Hmm, ik zit erover na te denken of hij ooit 31 0-bits zal returnen, maar het lijkt me wel. Die 64-bits waarde kan (mag) iig. nooit 0 worden. Je kunt de periode verlengen door bits te folden, dus iets als:
return (((int)(next >> 21)) ^ ((int)(next >> 30))) & DJ_RAND_MAX;

geloof me, de slimme meneren hebben hier vast wel goed over nagedacht hoor

[Verwijderd]

Op dinsdag 11 september 2001 15:19 schreef OiSyN het volgende:
geloof me, de slimme meneren hebben hier vast wel goed over nagedacht hoor

Knuth legt in het zelfde hoofdstuk uit dat bitfolding een methode is om bits met een betere random-verdeling te genereren Dit is een "ruwe" rng, en er zullen op deze manier bepaalde wetmatigheden in de volgordes van de gegenereerde bits te ontdekken zijn. Door truuks als bitfolding werk je die voorspelbaarheden weg. Je moet dan wel oppassen dat je enkel bits uit een goede range gebruikt (dus niet de hoogstwaardige of laagstwaardige bits).

<edit>
Dit komt uit mijn rng, en het zorgt voor een meer dan 3x zo goede verdeling dan wanneer ik de ruwe seeds retourneer:

code:

unsigned long ret= _seed[_idx++];
ret^= ret >> 11;
ret^= (ret << 7) & 0x9d2c5680;
ret^= (ret << 15) & 0xefc60000;
ret^= ret >> 18;
return ret;

</edit>