random getal berekenen uit random bytes

[Anoniem: 302117]

Hoi,
Voor ik begin, deze vraag is niet via google te zoeken, ik zou niet weten met welke zoektermen. Het is een niet zo algemeen probleempje.

Het probleem: ik wil een alternatief voor de random generator (van Borland c++builder) door gebruik te maken van data van www.random.org. Je kan van die server per dag een bepaald quota van random bits downloaden (een random bit is 0 of 1). Ik maak daarvoor op disk een bestand aan met random bytes.

Maar hoe bereken je nu een random getal tussen 0 en n uit die bytes?

Ik had eerst dit (de code is niet letterlijk maar je begrijpt een beetje wat ik wilde):

code:

  int random(n)
  {
  unsigned char num = 0;
  for (int i = 0; i < n / 256; i++)
    {
    fread(&num, 1, 1, randdata);
    m += num;
    }
  int p = n % 256;
  if (p)
    {
    fread(&num, 1, 1, randdata);
    m += num % p;
    }
  return m;
  }

Deze code gebruikt echter voor een getal > 512 al 3 bytes, dus klopt niet helemaal.
Ik moet dus waarschijnlijk iets met bitshifting of vermenigvuldigen doen, maar ik kom er niet uit.
Alvast bedankt. Ben benieuwd.

Edit:
Ik wil de range wel beperken tussen 0 en MAX_INT, dan heb ik dus per getal 1 tot 4 bytes nodig.
0-255 1 byte
0-65535 2 bytes
etc.
Kan ik het gevonden getal in die range dan 'gewoon' modulus 'n' doen?

[ Voor 8% gewijzigd door Anoniem: 302117 op 22-04-2012 20:34 ]

[spotke]

Zoiets?

code:

// http://www.codeproject.com/Tips/53433/BitArray-in-C
typedef struct {
    unsigned int bit : 1;
} Bit;

//BitArray structure.

typedef struct {
    Bit bitValues[32];
} BitArray; 

int random(int n)
{
    int numBits = (int)( ceil( log(n) / log(2) ) );
    int num = 0;
    int i;
    BitArray randData;

    for (i = 0; i < numBits; i++)
    {
        if (randData.bitValues[i].bit)
            num += pow(2, i);
    }

    return num % n;
}

Uit de losse pols, dus compileert wss nog niet eens... Maar zo zou ik het proberen

[Anoniem: 302117]

Thx.
Jee.. Cryptisch met die logs()..
Weet niet of het werkt maar ik zie dat je in ieder geval op het end ook die modulus doet.

Volgens mij werkt dit ook:

code:

int random(int n)
  {
  int numbytes = 4;
  if (n < 256) numbytes = 1;
  if (n > 255 && n < 65536) numbytes = 2;
  if (n >= 65535 && n < (1 << 24)) numbytes = 3;
  unsigned num = 0;
  for (int i = 0; i < numbytes; i++)
    {
    unsigned char x;
    fread(&x, 1, 1, randdata);
    num += x << (8 * i);
    }
  return num % n;
  }

Alleen die if's zou eleganter kunnen.

[RobIII]

Anoniem: 302117 schreef op zondag 22 april 2012 @ 20:08:
(een random bit is 0 of 1)

No shit; ik heb nog geen andere bits gezien

Anoniem: 302117 schreef op zondag 22 april 2012 @ 20:08:
Ik maak daarvoor op disk een bestand aan met random bytes.

Dit volg ik even niet; als ik hier kijk krijg je gewoon random bytes; ik heb nog niet gezien dat je ergens "losse bits" krijgt aangeleverd. En dat kan ook niet. 800 "losse bits" achter mekaar zijn gewoon 100 bytes. Misschien dat je wel < 8 bits kunt opvragen maar dan krijg je dus gewoon een byte met de eerste 4 bits 0 ofzo.

Anoniem: 302117 schreef op zondag 22 april 2012 @ 20:08:
Maar hoe bereken je nu een random getal tussen 0 en n uit die bytes?

Neem het minimum aantal bytes dat je nodig hebt voor je random getal en doe dat, inderdaad, modulus max_rand.
My bad WVL_KsZeN in "random getal berekenen uit random bytes"

[ Voor 4% gewijzigd door RobIII op 22-04-2012 21:30 ]

[Anoniem: 302117]

RobIII schreef op zondag 22 april 2012 @ 21:16:
[...]Dit volg ik even niet; als ik hier kijk krijg je gewoon random bytes; ik heb nog niet gezien dat je ergens "losse bits" krijgt aangeleverd. En dat kan ook niet. 800 "losse bits" achter mekaar zijn gewoon 100 bytes. Misschien dat je wel < 8 bits kunt opvragen maar dan krijg je dus gewoon een byte met de eerste 4 bits 0 ofzo.

Ik werk ook niet met bits, dat is niet praktisch met opslaan, ik maak een file met bytes aan (en gebruik dus sommige bits niet bij een 'berekening').

Edit: je kan gewoon losse bits via de api opvragen hoor:
http://www.random.org/int...se=2&format=plain&rnd=new
De catch is dat je alle getallen als strings terugkrijgt.

Neem het minimum aantal bytes dat je nodig hebt voor je random getal en doe dat, inderdaad, modulus max_rand.

Ja dus toch.

[ Voor 11% gewijzigd door Anoniem: 302117 op 22-04-2012 21:25 ]

[WVL_KsZeN]

Let even op met het gebruik van modulus!

Je zegt dat je maar 8 bits nodig hebt voor getallen t/m 255, maar op de manier waarop je het wilt gebruiken krijg je geen goede random getallen..

voorbeeld : je wilt een random getal t/m 254. De kans op waarde 0 is nu 2x zo groot als de de kans op de rest van de waardes! (bedenk zelf eens waarom). Er is op internet echt heel veel te vinden over hoe je moet omgaan met random getallen. Als je al de moeite neemt om random numbers van random.org op te vragen, moet je het daarna iig niet verpesten met slechte verdere verwerking...

Oh, de range 0-255 schalen (door waardes te delen) naar de range die je wilt hebben geeft hetzelfde soort probleem, door afrondingsproblemen gaan sommige waardes vaker voorkomen dan andere.

[ Voor 14% gewijzigd door WVL_KsZeN op 22-04-2012 21:27 ]

[Anoniem: 302117]

WVL_KsZeN schreef op zondag 22 april 2012 @ 21:25:
voorbeeld : je wilt een random getal t/m 254. De kans op waarde 0 is nu 2x zo groot als de de kans op de rest van de waardes!

Dus toch niet..

Niet modulus, wat dan wel? Iets met bitwise and?

[ Voor 3% gewijzigd door Anoniem: 302117 op 22-04-2012 21:27 ]

[TweakPino]

Anoniem: 302117 schreef op zondag 22 april 2012 @ 21:19:
Ja dus toch.

Niet helemaal. Het werkt, maar je random functies is dan niet uniform verdeeld.

Stel je wilt een dobbelsteen simuleren met een random waarde tussen [0..6) (inclusief 0, exclusief 6). Je neemt hiervoor 3 bits, en je resultaat is een waarde tussen [0..8). Doe je dit modulo 6, dan is je verdeling als volgt:

code:

0..1  2/8
2..5  1/8

Oftewel je functies is "niet helemaal random", 0 en 1 komen twee maal zo vaak voor dan dan de andere getallen. Hoe het dan wel moet, dat weet ik ook niet

[WVL_KsZeN]

De makkelijkste manier lijkt me het volgende algoritme :

stel je wilt een getal van 0 t/m a, en je random nummers lopen van 0 tm 255. De kans op waarde 0,1,2,...,255 is even groot. De kans op waarde 0,1,2...a is dus ook even groot.

code:

x = rnd_van_random.org
a = maximale waarde random nummer

while (x>a) { x = rnd_van_random.org }
return x

nadeel is dat je soms extra random nummers op moet vragen. Wel kun je deze kans verkleinen door bits weg te gooien uit je random getallen. Als je een getal van 0 tm 99 wilt, gebruik je bvb maar 7 bits van je random getal. Dan hoef je maar in 28/128 gevallen een nieuw getal op te vragen.

Er zullen vast betere methodes zijn, maar bij deze is het in ieder geval inzichtelijk wat er gebeurt, en dat de kansen even groot zijn voor alle waardes.

[dcm360]

Je neemt de kleinste veelvoud van 6 die gelijk is aan een macht van 2, en je verdeeld de range van het resultaat over de 6 mogelijkheden.
(in het geval dat je 6 gevallen wilt onderscheiden)

[ Voor 3% gewijzigd door dcm360 op 22-04-2012 21:37 ]

[Marcks]

Het makkelijkst is om overbodige informatie gewoon weg te gooien. Je wilt een willekeurig getal y tussen 0 en 254 afleiden uit een willekeurig getal x tussen 0 en 255. Het is meteen duidelijk dat niet alle waarden van x dusdanig naar y gemapt kunnen worden dat je een uniforme verdeling overhoudt.

Gebruik de modulo van een getal dat een geheel aantal keer in de range van je bron past. Heb je acht willekeurige bits, dan kun je mod 256, 128, 64 etc. gebruiken. Neem de kleinste waarde groter dan je max_rand. Het resultaat kan groter zijn dan max_rand. Pak in dat geval een nieuwe reeks bits en probeer het opnieuw.

[Anoniem: 302117]

Marcks schreef op zondag 22 april 2012 @ 21:39:
Het makkelijkst is om overbodige informatie gewoon weg te gooien. Je wilt een willekeurig getal y tussen 0 en 254 afleiden uit een willekeurig getal x tussen 0 en 255. Het is meteen duidelijk dat niet alle waarden van x dusdanig naar y gemapt kunnen worden dat je een uniforme verdeling overhoudt.

Ik bewonder je beschrijving van het probleem, je suggestie voor de oplossing wat minder.

Als het gaat om info weglaten, kan ik dan niet gewoon een bitwise and met max_rand doen?

<still struggling with a dangling bit>

[A_K]

Je kan de data hergebruiken, maar dat wordt ingewikkeld (stel dat je 0-255 terug kan krijgen, en je wilt een getal tussen 0-239, dan kan je op het moment dat het getal groter is dan 239 er 239 vanaf trekken, en dan heb je een willeurig getal tussen de 1 en 16. Als je er dan 2 van hebt doe je de eerste keer 16 en tel je de tweede er bij, en je hebt weer een willekeurig getal tussen 0 en 272 wat je weer kan gebruiken. Maar dat is dus ingewikkeld)

Ik zou het bij WVL_KsZeN oplossing houden. Die is simpel en duidelijk.

[Soultaker]

dcm360 schreef op zondag 22 april 2012 @ 21:36:
Je neemt de kleinste veelvoud van 6 die gelijk is aan een macht van 2, en je verdeelt de range van het resultaat over de 6 mogelijkheden.

Jij meent dat er een macht van twee bestaat die een veelvoud is van zes? Sla de hoofdstelling van de rekenkunde er nog eens op na.

[Henk007]

Waarom zou je opnieuw het wiel uitvinden, gebruik een bestaand random number algoritme en maak gebruik van de input van random.org als seed (x_k)
Bijvoorbeeld:
Wikipedia: Lehmer random number generator

[ Voor 4% gewijzigd door Henk007 op 22-04-2012 23:01 ]

[dcm360]

Soultaker schreef op zondag 22 april 2012 @ 22:45:
[...]

Jij meent dat er een macht van twee bestaat die een veelvoud is van zes? Sla de hoofdstelling van de rekenkunde er nog eens op na.

Woeps, daar was ik me even een partij niet wakker

[WVL_KsZeN]

Toch blijf ik het apart vinden hoe makkelijk sommigen over dit soort dingen denken. Ik geef direkt toe : ik gebruik ook heel vaak gewoon modulus om een getal in een range te krijgen. Maar dat gaat dan om zaken waar het mij (en voor het resultaat) niet uitmaakt als de uniformiteit niet helemaal klopt. Vaak gaat het dan ook om kleine getallen (0...1000 zeg) vergeleken met de int32 van de random generator, zodat de uniformiteit nauwelijks inboet.

Maar als je er echt goed werk van wil maken en zelfs getallen op gaat vragen moet je dus opletten bij soort soort geintjes.

* WVL_KsZeN vraagt zich wel eens of waarom hij altijd zonodig de wijsneus uit moet hangen..

[Soultaker]

A_K schreef op zondag 22 april 2012 @ 22:41:
Je kan de data hergebruiken, maar dat wordt ingewikkeld (stel dat je 0-255 terug kan krijgen, en je wilt een getal tussen 0-239, dan kan je op het moment dat het getal groter is dan 239 er 239 vanaf trekken, en dan heb je een willeurig getal tussen de 1 en 16. Als je er dan 2 van hebt doe je de eerste keer 16 en tel je de tweede er bij, en je hebt weer een willekeurig getal tussen 0 en 272 wat je weer kan gebruiken. Maar dat is dus ingewikkeld)

Juist. De truc is om niet alleen bij te houden wat je huidige getal is, maar ook uit welk bereik je aan het selecteren bent. Als je een uniform random getal i hebt uit een bereik \[0..n) (dus 0 tot en met n-1), en j is een random bit, dan is 2*i + j een random bit uit het bereik \[0..2n).

Als je random bereik \[0..m) groter dan (of gelijk) is aan het doelbereik \[0..n) (bijvoorbeeld \[0..8) is groter dan \[0..6)) en je hebt een random getal i dat in beide bereiken valt, dan kun je dat opleveren. Maar wat nu als het getal i buiten het doelbereik valt? In dat geval gooit WVL_KsZeN het resultaat weg en begint opnieuw, maar je kunt ook terugschalen naar i - n met bereik \[0..m-n) om niet onnodig entropie weg te gooien.

Concrete implementatie van dit idee:

Python:

def next_number(n):  # gewenste bereik [0..n)
        assert n > 0
        m = 1  # huidige random bereik [0..m)
        i = 0  # huidige random waarde (0 <= i < m)
        while m < n:
                m = 2*m
                i = 2*i + next_bit()
                if i >= n:
                        m -= n
                        i -= n
        return i

edit:
Ik weet niet zeker of dit resultaat optimaal is voor het genereren van een enkel getal n trouwens. Als je meerdere getallen nodig hebt is het sowieso efficiënter om ze in één keer te genereren. Als je vier zeszijdige dobbelstenen wil rollen bijvoorbeeld, kost het minder bits om één keer een getal tot 6⁴ = 1296 te genereren dan vier keer een getal tot zes. Maar dan nog is bovenstaande aanpak nuttig.

[ Voor 10% gewijzigd door Soultaker op 22-04-2012 23:24 ]

[Anoniem: 302117]

Ik zie niet hoe de oplossing van WVL_KsZeN werkt, tenminste niet volgens dat stukje code. Met 'x' wordt daar niets gedaan behalve opgevraagd.

Project gaat in de ijskast..

[WVL_KsZeN]

Simpel :

vraag een random getal op. is het random getal groter dan je bereik? vraag een nieuw getal op. herhaal.

Die van soultaker ziet er ook wel goed uit!

[Anoniem: 302117]

Op de een of andere manier heb ik toch het idee dat als je steeds maar nieuwe random getallen opvraagt tot je er een krijgt die je bevalt ook niet echt een goede manier van evenwichtige distributie is. Nog los van efficientie, heb je een getal van 31 bits nodig ben je 4 bytes per poging kwijt.

Die methode van Soultaker ga ik eens testen.

[Grijze Vos]

Anoniem: 302117 schreef op maandag 23 april 2012 @ 09:03:
Op de een of andere manier heb ik toch het idee dat als je steeds maar nieuwe random getallen opvraagt tot je er een krijgt die je bevalt ook niet echt een goede manier van evenwichtige distributie is.

Tuurlijk wel. De getallen die je weggooit tellen niet mee in de distributie.

En qua efficientie valt het ook mee. Worst case ben je 2x zoveel data aan het gebruiken dan theoretisch nodig. In de praktijk zal dit uitkomen op een procent of anderhalf keer zoveel.

[ Voor 19% gewijzigd door Grijze Vos op 23-04-2012 09:13 ]

[Anoniem: 302117]

Hm, misschien niet. Maar dan zit ik nog wel met iets als random(3) wat zomaar 80 pogingen kan vragen.
Edit: we zijn het niet eens over worst case zie ik.

[ Voor 20% gewijzigd door Anoniem: 302117 op 23-04-2012 09:19 ]

[WVL_KsZeN]

nee, als je random (3) wilt hebben, gebruik je maar 2 bits. (zit niet in mijn code, maar kun je zelf vast wel schrijven!). Bij random(3) (ik lees het als maximale waarde 3), dan heb je altijd succes als je maar 2 random bits gebruikt.

voorbeeld : je wilt random (6), dan gebruik je maar 3 random bits. Als de random waarde die je krijgt 7 is, dan vraag je 3 nieuwe bits op.

Bij elk getal dat je wilt hebben heb je kans dat het mis gaat, als je bijvoorbeeld random(62) wilt hebben en je gebruikt daarvoor 6 bits, dan heb je een kans van 1/64 dat het mis gaat (je krijgt toevallig waarde 63 terug). Wil je random (32), dan moet je in 50% van de gevallen (waardes 33-63)een nieuw getal opvragen. Gemiddeld moet je dus in 25% van de gevallen een nieuw getal opvragen, valt dus reuze mee!

[ Voor 16% gewijzigd door WVL_KsZeN op 23-04-2012 09:41 ]

[Anoniem: 302117]

Ok, is me duidelijk nu. Ik ga het eens proberen.

[Zoijar]

Omgaan met randomness is veel lastiger dan men denkt. Waarom gebruik je niet gewoon een bestaande RNG? Het lijkt er namelijk op of je makkelijk een veel grotere fout er in laat sluipen door een slechte implementatie dan het verschil tussen atmosferische ruis en een degelijke RNG.

[Anoniem: 302117]

Mee eens. Alleen je aanname is dat het een slechte implementatie zal zijn en dat is nog niet gezegd.

[Zoijar]

Anoniem: 302117 schreef op maandag 23 april 2012 @ 10:43:
Mee eens. Alleen je aanname is dat het een slechte implementatie zal zijn en dat is nog niet gezegd.

Niettemin had je al verschillende bugs aanvankelijk niet opgemerkt

[Anoniem: 302117]

Als je het beter kan, wat let je?

[Grijze Vos]

Het is niet zijn code, vriend.

Hij heeft echter wel gewoon gelijk. Als het gebruik van random.org ervoor zorgt dat jouw implementatie bugs bevat die de uniformiteit van je generator aantast, dan is dat veel erger dan het probleem van pseudo-randomness van een reguliere rng.

[dcm360]

Vaak wil je gewoon een uniform verdeeld random getal, en in dat geval voldoen er heel erg veel standaard implementaties. random.org beweert overigens dat de getallen die ze opleveren niet strict uniform verdeeld zijn.

[Anoniem: 302117]

Grijze Vos schreef op maandag 23 april 2012 @ 10:50:
Het is niet zijn code, vriend.

Hij heeft echter wel gewoon gelijk. Als het gebruik van random.org ervoor zorgt dat jouw implementatie bugs bevat die de uniformiteit van je generator aantast, dan is dat veel erger dan het probleem van pseudo-randomness van een reguliere rng.

Ik geef hem ook gelijk.
Maar tot nu toe zijn hier nog geen implementaties van mij besproken behalve m'n allereerste vingeroefening die inderdaad niet klopte. Dus lever die kritiek dan op de mensen die de oplossingen proberen aan te leveren als je dat nodig vind.

[Zoijar]

Anoniem: 302117 schreef op maandag 23 april 2012 @ 10:45:
Als je het beter kan, wat let je?

Ik gebruik gewoon een Mersenne twister inderdaad, en denk dat ik nooit een project zal doen waar de uniformiteit daarvan een daadwerkelijk probleem op zal leveren. Maar mijn excuses, het was maar een tip. Je vroeg hier tenslotte om hulp en input...

[Soultaker]

Anoniem: 302117 schreef op maandag 23 april 2012 @ 09:18:
Hm, misschien niet. Maar dan zit ik nog wel met iets als random(3) wat zomaar 80 pogingen kan vragen.

Dat is onvermijdelijk. Je kunt niet door een vast aantal keer met één muntje te gooien tussen drie verschillende mogelijkheden kiezen (met uniforme kansverdeling). Er bestaat altijd een theoretische mogelijkheid dat je "oneindig" vaak moet gooien, maar dat gebeurt bijna nooit (ja, dit is een serieuze wiskundige term ).

Wat belangrijker is, is de verwachtingswaarde. Voor random(3) heb je gemiddeld 8/3 bits nodig. Dat valt natuurlijk wel te overzien. De kans dat je 80 bits nodig hebt is 1/2⁸⁰; dat is astronomisch klein.

WVL_KsZeN schreef op maandag 23 april 2012 @ 09:34:
Bij random(3) (ik lees het als maximale waarde 3), dan heb je altijd succes als je maar 2 random bits gebruikt.

Ik ging er vanuit dat random(3) kiezen uit drie mogelijkheden betekende (en het resultaat is dan dus 0, 1 of 2).

Grijze Vos schreef op maandag 23 april 2012 @ 10:50:
Als het gebruik van random.org ervoor zorgt dat jouw implementatie bugs bevat die de uniformiteit van je generator aantast, dan is dat veel erger dan het probleem van pseudo-randomness van een reguliere rng.

Op zich heb je met een andere PRNG hetzelfde probleem; die zal namelijk ook een vast bereik hebben. Het enige verschil is dat een uitgebreidere library waarschijnlijk al routines bevat om het resultaat op te schalen. Het zijn dus die routines die je wil hebben; niet zozeer de bron van entropie.

[ Voor 14% gewijzigd door Soultaker op 23-04-2012 22:36 ]

[WVL_KsZeN]

Waar heb je het eigenlijk voor nodig? Kan me eigenlijk niet voorstellen dat iemand die random getallen serieus aan wil/moet pakken daarvoor info zoekt op GoT. Is het gewoon een hobby-dingetje?

Tip : lees ook eens The Art of Computer Programming van Donald Knuth, er is een heel hoofdstuk over random getallen.

[Anoniem: 302117]

Waar heb je het eigenlijk voor nodig?

Mijn software heeft een scripttaal http://astrobasic.jcremers.com/?lan=nl en die wordt wel door mensen gebruikt voor semi-wetenschappelijke projectjes waaronder statistisch onderzoek e.d. waar random() vaker gebruikt wordt. Ik wilde een alternatief voor de randomgenerator van Borland C++builder. Bv als je dan met 0 seed dat het dan van data van randomorg gebruik maakt.
Alleen random.org vraagt dat je zoveel mogelijk je data in 1 keer opvraagt, dat scheelt natuurlijk in http requests voor die server, anders kon ik gewoon random ranges opvragen zoals het uitkomt.
Ik heb het projectje voorlopig in de ijskast gezet want ik heb er even gewoon niet zoveel zin meer in. Wie weet kom ik er tzt op terug.

De kans dat je 80 bits nodig hebt is 1/280; dat is astronomisch klein.

Ja ik rekende in bytes. Als je dit een beetje efficient wil doen moet je idd wel met bits gaan rekenen en iets als getnextbits(int) maken. Aantal bits wat je nodig hebt kan trouwens makkelijk met strlen(itoa(nummer, string, 2)).

[ Voor 17% gewijzigd door Anoniem: 302117 op 24-04-2012 12:56 ]

[MSalters]

Die laatste regel Serieus, als je die echt meent dan moet je je gewoon bij de bestaande RNG houden. De kans dat je met jouw ervaring de bestaande RNG van Borland verbetert is echt nihil. Dat geldt nog steeds als je probeert random.org te wrappen; daarbij kan nog steeds bijzonder veel fout gaan.

[Henk007]

Inderdaad, zoals ik in mijn eerste reactie al schreef, opnieuw het wiel uitvinden is vergeefse moeite.
Ik stelde al een eenvoudige PRNG voor, maar Zoijar heeft een moderner en meer state of the art voorstel gedaan, de Mersenne twister.
Kopieer gewoon een implementatie daarvan in je code en je bent klaar. Eventueel seeden met data van random.org.
Ik zie zojuist dat de default prng in Borland C++ een LCG is:
Wikipedia: Linear congruential generator

astrologie

[ Voor 27% gewijzigd door Henk007 op 24-04-2012 22:56 ]

[Nick The Heazk]

Henk007 schreef op dinsdag 24 april 2012 @ 22:43:
Inderdaad, zoals ik in mijn eerste reactie al schreef, opnieuw het wiel uitvinden is vergeefse moeite.
Ik stelde al een eenvoudige PRNG voor, maar Zoijar heeft een moderner en meer state of the art voorstel gedaan, de Mersenne twister.
Kopieer gewoon een implementatie daarvan in je code en je bent klaar. Eventueel seeden met data van random.org.

Nog een beter idee: gebruik gewoon Boost random en je bent klaar. Het is me ook een raadsel waarom de TS het warm water wil heruitvinden?

[Zoijar]

Nick The Heazk schreef op woensdag 25 april 2012 @ 00:40:
Nog een beter idee: gebruik gewoon Boost random en je bent klaar. Het is me ook een raadsel waarom de TS het warm water wil heruitvinden?

boost::random::mt19937 is een mersenne twister inderdaad. En dan heb je daar meteen verschillende range functies bij etc.

ALGLIB heeft ook veel support voor randomness: http://www.alglib.net/tra...anual.cpp.html#unit_hqrnd

Maar ik kan me voorstellen dat je geen dependency wilt toevoegen, dan is een implementatie kopieren wel een goed idee. Ik gebruik zelf ook steeds minder boost, zeker als ik een (bijna) C++11 compiler als gcc kan gebruiken.

[.oisyn]

Boost::random zit ook min of meer in TR1, die al met veel pre-C++11 compilers shipt (zoals Visual Studio 2005 SP1 en GCC 4.1)

't Mooie van die library is overigens dat de RNG los staat van de distributor. Je zou dus prima je eigen random.org implementatie kunnen maken die gewoon de getallen produceert (in chunks van 32 bits bijvoorbeeld), en daar een uniform_int_distribution<> oid op leggen die ervoor zorgt dat je een goede random distributie krijgt in je gewenste range.

[ Voor 62% gewijzigd door .oisyn op 25-04-2012 12:44 ]

[Patriot]

Soultaker schreef op maandag 23 april 2012 @ 22:31:
[...]

Wat belangrijker is, is de verwachtingswaarde. Voor random(3) heb je gemiddeld 8/3 bits nodig. Dat valt natuurlijk wel te overzien. De kans dat je 80 bits nodig hebt is 1/2⁸⁰; dat is astronomisch klein.

Euh.. wacht.. Wat voor getallen ben je nou precies aan het rondstrooien? Het ging om 80 keer proberen, dat is bij een random(3) volgens mij 160 bits? Immers, om 0, 1 en 2 te kunnen maken heb je steeds twee bits nodig. Je moet je in 25% van de gevallen je resultaat weggooien (dat is binair 11, dus 3), dus dan is het toch 1/4⁸⁰, waarbij je 160 bits gebruikt heb?

[MSalters]

80 bits = 40 pogingen = 1/4⁴⁰ = 1/2⁸⁰.

[Patriot]

MSalters schreef op woensdag 25 april 2012 @ 18:21:
80 bits = 40 pogingen = 1/4⁴⁰ = 1/2⁸⁰.

Het ging om 80 pogingen, niet om 80 bits. Daarom is het 80 pogingen = 160 bits = 1/4⁸⁰ ( = 1/2¹⁶⁰)

[ Voor 3% gewijzigd door Patriot op 25-04-2012 18:22 ]

[.oisyn]

Dat is niet wat Soultaker zei:

De kans dat je 80 bits nodig hebt is 1/2⁸⁰; dat is astronomisch klein

Alle berekeningen in de topic kloppen gewoon, het enige is dat Soultaker een poging interpreteerde als een bit.

[ Voor 48% gewijzigd door .oisyn op 26-04-2012 10:21 ]

[Patriot]

.oisyn schreef op donderdag 26 april 2012 @ 10:18:
Dat is niet wat Soultaker zei:

[...]

Alle berekeningen in de topic kloppen gewoon, het enige is dat Soultaker een poging interpreteerde als een bit.

Ja, derp, dat snap ik, daarom zei ik ook dat het om 80 keer proberen ging. Het ging mij verder ook vooral om de 8/3 bits die hij nodig dacht te hebben. Buiten het feit dat het niet mogelijk is, waar komt het vandaan?

[.oisyn]

Als het daar vooral om ging, waarom kwam dat dan niet terug in je post, DERP?
Hij zei overigens "gemiddeld". Het is ook niet mogelijk dat een huishouden 1,5 kinderen heeft. Waar die 8/3 vandaan komt snap ik niet goed - ik zou zeggen dat je gemiddeld ²log(3) bits nodig hebt.

No, that ain't right. Je vraagt 2 bits. In 1 van de 4 gevallen dat je om bits vraagt, moet je opnieuw om bits vragen. Gemiddeld vraag je dus om 3/4*2 + 1/4*(2 + 3/4*2 + 1/4*(2 + 3/4*2 + 1/4*(...))) = 8/3 bits.

[ Voor 84% gewijzigd door .oisyn op 26-04-2012 15:04 ]