[PASCAL] random reeksen

[GeNiTaLiX]

Voor school moet een random programma maken , dat getallen genereerd, en er een verband tussen moet gaan vinden, daarna zal ik via de rekenmachien de kans calculeren en zo laten zien, dat het random niet geheel random is, maar nu alleen het probleem, hoe vind ik die reeksen? Ik kan wel random getallen aan laten maken, maar moet ik deze dan in een txt laten zetten achter elkaar en zo het programma laten scannnen op dubbele reeksen of op de hoeveelheid dat een getal er in voor komt, 't zou fijn zijn als ik wa hulp kreeg,

Thx

[Creepy]

Wat heb je zelf al geprobeerd? Wat lukte hier niet mee? Wat zijn je eigen ideeen?

Zoals je je nu topic opent geef je te weinig info. We gaan er hier vanuit dat je zelf al het 1 en ander hebt geprobeerd. Daarnaast zou je met de lesstof van je school al genoeg informatie moeten hebben om je opdracht tot een goed einde te brengen.

Zie ook P&W FAQ - De "quickstart" voor wat we eigenlijk van een topicstart verwachten.

[GeNiTaLiX]

Op school krijgen wij hier geen informatie over, dit is namelijk voor een praktische opdracht wiskunde , ik kom er namelijk niet meer uit. Ik heb een reeks van 1 tm 10 laten maken en het programma laten tellen hoe vaak deze getallen worden gebruikt, dus verdeeld

code:

USES crt;

VAR r,t,a,b,c,d:integer;

BEGIN
  a:=0;
    REPEAT
      t:=t+1;
      r:=random(10);
      IF r=1 THEN a:=a+1;
    UNTIL t=100;
  writeln('aantal 1: ',a);
  readln;
END.

Zo dus van 1 t/m 10, maar het leek me dat ik hier verkeerd over het zal waarschijndelijk anders moeten.

[Creepy]

Over het genereren van random getallen, zoals de random functie doet, is het 1 en ander te vinden via google. In het kort: na verloop van tijd gaat de reeks getallen zich weer herhalen. Wanneer dat gebeurt is afhankelijk van het gekozen algoritme in de random() functie.

Je kan dus op twee manieren bewijzen dat het niet echt random is:
1 - achterhaal het algoritme en bereken daarna met de rekenmachine het volgende random getal
2 - Wacht tot de reeks zich gaat herhalen. Dit gebeurt vanzelf Het kan wel enige tijd en een flink aantal getallen duren

[Daos]

Als je even via google had gezocht, dan vond je onder andere deze pagina waar je kan lezen hoe random werkt. Er zijn zelfs voorbeelden te vinden.

[GeNiTaLiX]

Dus zou het dan helpen, als ik een reeks neem van nul en een. Zodat deze zichzelf gaat herhalen na verloop van tijd ? .. maar dit betekend dus dat ik deze reeks moet opslaan in een txtje en dan na een lange tijd zal dezelfde reeks er weer staan . .vanaf het begin .. en so on ?

iig bedankt

[EXX]

Moet je niet de verdeling van de random getallen registeren in bv. een array?

Delphi:

const MAX_RND_NUM = 10;
     MAX_DRAW      = 100;

type verdeling = array[1..MAX_RND_NUM] of integer;

var index, rnd_num : integer;
    rnd_num_verdeling : verdeling;

begin

  {Array initialiseren op 0 }

   for index := 1 to MAX_RND_NUM do 
     rnd_num_verdeling[index] := 0;

   for index := 1 to MAX_DRAW do             { trek 100 random nummertjes }
     begin
         rnd_num := random(MAX_RND_NUM);        { trek een getal van 1..10 }
         rnd_num_verdeling[rnd_num] := rnd_num_verdeling[rnd_num] + 1;
     end;

   { De array bevat nu de verdeling }

  for index := 1 to MAX_RND_NUM do
    writeln('Aantal malen ',index:2,' :  ',rnd_num_verdeling[index]:3);
end.         

edit:

Volgens mij ben ik en te laat en en heb ik niet helemaal begrepen

[ Voor 7% gewijzigd door EXX op 08-02-2005 14:02 ]

[GeNiTaLiX]

Ja daar had ik nu ook al last van , hij blijft steeds de zelfde results geven na elke run:

code:

Aantal malen  1 :   10
Aantal malen  2 :    9
Aantal malen  3 :   11
Aantal malen  4 :   12
Aantal malen  5 :    9
Aantal malen  6 :    6
Aantal malen  7 :    8
Aantal malen  8 :   13
Aantal malen  9 :   13
Aantal malen 10 :    0

[GeNiTaLiX]

zelfde geval bij mijn proggie -.- .. maar als ik bijvoorbeeld

code:

PROCEDURE start;
BEGIN
  x:=0;
  t:=0;
  a:=0;
  b:=0;
  randomize;
  writeln('calculating');
    WHILE t < 100 DO
      BEGIN
        x:=random(2);
        t:=t+1;
         IF x=1 THEN a:=a+1 ELSE b:=b+1;
      END;
   writeln('kop:',b);
   writeln('munt:',a);
   readln;
   start;
END;

zoiets doe pakt ie de random code wel, zou ik hier ook een reeks uit kunnen halen ?

[EXX]

GeNiTaLiX schreef op dinsdag 08 februari 2005 @ 14:11:
Ja daar had ik nu ook al last van , hij blijft steeds de zelfde results geven na elke run:

Dat komt omdat de random generator opnieuw gestart wordt met dezelfde startwaarde, en dan krijg je dus ook dezelfde reeks. Wil je iedere keer een andere startwaarde, moet je een randomize function uitvoeren, zoals je dat ook in de laatste versie van je eigen progsel hebt gedaan, dus:

Delphi:

const MAX_RND_NUM = 10;
     MAX_DRAW      = 100;

type verdeling = array[1..MAX_RND_NUM] of integer;

var index, rnd_num : integer;
    rnd_num_verdeling : verdeling;

begin

  {Array initialiseren op 0 }

   for index := 1 to MAX_RND_NUM do 
     rnd_num_verdeling[index] := 0;

   randomize;  { set random startwaarde voor random generator }

   for index := 1 to MAX_DRAW do             { trek 100 random nummertjes }
     begin
         rnd_num := random(MAX_RND_NUM);        { trek een getal van 1..10 }
         rnd_num_verdeling[rnd_num] := rnd_num_verdeling[rnd_num] + 1;
     end;

   { De array bevat nu de verdeling }

  for index := 1 to MAX_RND_NUM do
    writeln('Aantal malen ',index:2,' :  ',rnd_num_verdeling[index]:3);
end.         

[ Voor 54% gewijzigd door EXX op 08-02-2005 14:44 ]

[riezebosch]

Ik denk dat je gewoon in een loopje een array moet vullen, en bij elke nieuwe waarde controleren of ie overeenkomt met de voorste. Wanneer dit het geval is, controleren of het volgende 'random' getal overeenkomt met de tweede. Enz... Zogauw je er een tegenkomt die niet overeenkomt begin je weer bij de eerste te kijken, want dan is je reeks blijkbaar niet gelijk. Als je op deze manier het einde van de reeks haalt kan je stoppen, en weet je hoeveel elementen er random gegenereerd kunnen worden.

[GeNiTaLiX]

hmm ander idee, als ik nu de getallen 0,1 doe en laat die 100000 genereren, tel ze bij elkaar op deel de uitkomst door 100000, en als deze niet op 0,5 uitkomt dan klopt er iets niet,

[EXX]

Dat zal altijd in de buurt van 0.5 liggen bij 100000 "trekkingen" . Ik denk dat het voorstel van riezebosch in de richting gaat.

edit: de cyclus van en randomgenerator is niet zo makkelijk te bepalen. Je kunt natuurlijk de eerste n getallen in een array zetten en dan vanaf n+1 gaan vergelijken met je array.

Probleem is dat je wel kunt vaststellen of je reeks weer gelijk is aan je array, maar dat wil niet zeggen dat dat ook geldt voor het volgende getal n+1 die je niet meer in je array hebt zitten.

Aan de andere kant heb je het probleem dat je de array niet groter mag zijn dan de cylcus, dan werkt het ook niet meer.

[ Voor 68% gewijzigd door EXX op 08-02-2005 14:50 ]

[GeNiTaLiX]

dus een array met getallen 0 t/m 9 bijv 235633532 en met deze array zoeken naar dubbele en kijken welke getallen daar achter komen. een idee hoe ik dit laat doen ik ben een noobje in pascal

[Creepy]

EXX schreef op dinsdag 08 februari 2005 @ 14:46:
Aan de andere kant heb je het probleem dat je de array niet groter mag zijn dan de cylcus, dan werkt het ook niet meer.

Tuurlijk wel, op het moment dat de je array vult kun je toch vergelijken met het begin van de array?

[Creepy]

GeNiTaLiX schreef op dinsdag 08 februari 2005 @ 14:57:
dus een array met getallen 0 t/m 9 bijv 235633532 en met deze array zoeken naar dubbele en kijken welke getallen daar achter komen. een idee hoe ik dit laat doen ik ben een noobje in pascal

Ja ho ff. Dit is echt basis van pascal. Array items vergelijken is echt niet zo moelijk, en een reeks vergelijken is dat nou ook niet. Met een while loop o.i.d moet je een heel eind kunnen komen.

We verwachten hier dat je de basis van een ontwikkelomgeving onder de knie hebt, of zelf onder de knie kunt krijgen.

[riezebosch]

Maar de vraag is dan natuurlijk of als de reeks zich herhaald heeft deze het de volgende keer weer zal doen Met een echte random-number-generator is het natuurlijk niet uitgesloten dat een bepaalde reeks zich herhaald.

_{Doet me denken aan het grapje wat ooit iemand hier in z'n sig had staan:}




Probleem is wel dat je vantevoren niet in kunt schatten hoe groot je array moet zijn.

[ Voor 29% gewijzigd door riezebosch op 08-02-2005 15:12 ]

[EXX]

Daarom denk ik niet dat de opdracht van de TS het bepalen van de cyclus van een random generator is, maar iets anders.

[riezebosch]

Nou, als je de cyclus aan kan tonen heb je (min of meer) het bewijs dat random niet echt random is. Gegeven de implementatie van de programmeeromgeving dan. En als je de cyclus weet, kan je ook weer het volgende getal voorspellen. Moet je natuurlijk wel eerst de cyclus opgebouwd hebben, en is dus ook iedere keer dat het programma opnieuw runt anders.

Het is dus inderdaad niet zo, zoals de TS zegt, dat je met je rekenmachientje kan voorspellen welk getal er nu zal komen.

[ Voor 51% gewijzigd door riezebosch op 08-02-2005 15:27 ]

[Verwijderd]

Ik zou niet tussen 0 en 9 laten genereren maar iets ruimer, tussen de 1 en de 255 bijvoorbeeld (dit getal is niet willekeurig gekozen, zie verderop).
Dan een reeks laten genereren van bijvoorbeeld 100000 getallen en een paar bewerkingen op loslaten:

- Bepaal van elk getal hoe vaak het in de reeks voorkomt. Gemiddeld verwacht je dat elk getal 100000/255 keer voorkomt.
Wat is de kans dat een getal 15x voorkomt? En 5x?
Bepaal welk getal het meest voorkomt en hoevaak dit dan voorkomt. Hoe groot is die kans?
Hetzelfde voor het getal dat het minst voorkomt. Hoe groot is die kans?

Ik weet niet hoe uitgebreid jouw statistiek is, maar je kunt berekenen tussen welke waarden de gegenereerde waarden moeten liggen om te zeggen dat je geen uitschieters hebt.

Verder kun je de reeks als bytes naar een file schrijven en deze zippen. Zip zoekt naar herhalende reeksen. Als zip de file kan compressen is hij niet random.

[EXX]

Ik heb even wat in elkaar gedraaid:

Delphi:

program random_reeks;
{*******************}

{****
 * Dit programma bepaalt de cyclus van de randomgenerator
 * Compiler: Turbo Pascal 3.0
 ****}

const MAX_RIJ = 10;
      MAX_TREKKINGEN = 10000000.0;
      MAX_RND = 10;

type  rij = array[1..MAX_RIJ] of integer;

var   vergelijkingsrij : rij;
      rndrij : rij;
      index : integer;
      teller : real;
      cyclus_rond : boolean;

begin
  { initaliseren }

  for index := 1 to MAX_RIJ do
    vergelijkingsrij[index] := random(MAX_RND);
  teller := MAX_RIJ;
  for index := 1 to MAX_RIJ do
    rndrij[index] := random(MAX_RND);

  repeat
    cyclus_rond := TRUE;

    index := 1;
    while cyclus_rond and (index <= MAX_RIJ )do
      begin
        cyclus_rond :=
          cyclus_rond and (vergelijkingsrij[index] = rndrij[index]);
        index := index + 1;
      end;

    if not(cyclus_rond)
      then
        begin
          for index := 1 to (MAX_RIJ - 1) do
            rndrij[index] := rndrij[index + 1];
          rndrij[MAX_RIJ] := random(MAX_RND);
          teller := teller + 1;
        end;

  until cyclus_rond or (teller > MAX_TREKKINGEN);

  if cyclus_rond
    then writeln('Cyclus : ',teller:7:0,' getallen.')
    else writeln('Geen cyclus gevonden in ',MAX_TREKKINGEN:7:0,' getallen');
end.

Toch krijg ik dat er geen cyclus wordt gevonden. Of good old Turbo 3 heeft een hele goede randomgenerator of er is iets mis met het progsel

[ Voor 3% gewijzigd door EXX op 08-02-2005 17:02 ]

[riezebosch]

Dat Zip zoekt naar herhalende reeksen is volgens mij redelijk achterhaald. Het zal misschien nog wel onderdeel uitmaken van de compressiemethode, maar er zijn al wel veel geavanceerdere. En waarom zou zelfs bij niet echt random elk getal wel evenvaak voor moeten komen?

@EXX: Misschien dat de reeks veel groter is dan 10.000.000

[ Voor 11% gewijzigd door riezebosch op 08-02-2005 15:38 ]

[RobIII]

Verwijderd schreef op dinsdag 08 februari 2005 @ 15:30:
Verder kun je de reeks als bytes naar een file schrijven en deze zippen. Zip zoekt naar herhalende reeksen. Als zip de file kan compressen is hij niet random.

Tja, als je zo een stelling gaat bewijzen
Zonder dat je de intrinsieke werking van Zip kent kun je hier natuurlijk geen uitspraken over doen. Als er 3x een 56-byte in m'n bestand achter elkaar staat (wat altijd kan), dan kan er misschien wel degelijk gecompressed worden. Misschien ook niet. Who knows. Tenzij je dus de exacte inwendige werking van Zip kent, of je eigen compressie schrijft mag je hier natuurlijk niet je uitspraken op staven (en al helemaal niet je wiskunde huiswerk )

[Verwijderd]

Pascal's Rnd functie is niet perfect random, zeker niet met alle waarden van RandSeed. Hier een bespreking:
http://www.merlyn.demon.co.uk/pas-rand.htm

[EXX]

het progsel een paar keer laten lopen:

code:

H:\PROGDEV\PASCAL>rndreeks
Geen cyclus gevonden in 100000000 getallen

H:\PROGDEV\PASCAL>rndreeks
Geen cyclus gevonden in 100000000 getallen

H:\PROGDEV\PASCAL>rndreeks
Cyclus : 54569448 getallen.

H:\PROGDEV\PASCAL>rndreeks
Cyclus : 63052312 getallen.

H:\PROGDEV\PASCAL>rndreeks
Cyclus : 30442008 getallen.

H:\PROGDEV\PASCAL>rndreeks
Cyclus :  786432 getallen.

H:\PROGDEV\PASCAL>rndreeks
Cyclus : 100663296 getallen.

H:\PROGDEV\PASCAL>

Blijkbaar wordt de randomgenerator (bij Turbo Pascal 3.0) niet default op 0 gezet bij het starten van het programma.

[eamelink]

EXX schreef op dinsdag 08 februari 2005 @ 16:30:
het progsel een paar keer laten lopen:

[code]
Blijkbaar wordt de randomgenerator (bij Turbo Pascal 3.0) niet default op 0 gezet bij het starten van het programma.

Als ik hem onder debian compile met fpc, dan vindt hij geen een keer een herhaling

[edit]
Na 700 runs nog steeds niet, ik stop maar

[ Voor 8% gewijzigd door eamelink op 08-02-2005 20:05 ]

[EXX]

het kan ook zijn dat de reeks van 10 die ik controleer te kort is (vandaar dat decyclus varieert) en er dus onterecht vanuit gegaan wordt dat de random generator opnieuw begint. Ik probeer het eens met een rij van 20.

[GeNiTaLiX]

Maar nu worden dus als het ware, een rij van 10 random nummers vergeleken met de getallen die erna komen, tot deze rij zich weer herhaalt. Dan laat het programma zien wanneer de herhaling plaatsvond.


Dus: de kans 0 tm 9 op 1 plaats kans van 1 op 10 dus 0.1
maar nu - - - - - - - - - - 10 plaatsen waar 0 t/m 9 op kan komen
hoe groot is de kans dat bijv 0 0 0 0 0 0 0 0 0 0 daar komt ?

code:

P(getal 0)= (10boven1)x(10boven1)x(10boven1)x(10boven1)x(10boven1)x(10boven1)x(10boven1)x(10boven1)x(10boven1)x(10boven1)
----------------------------------
(100boven10)

uitgerekend:

code:

 (10)*(10)*(10)*(10)*(10)*(10)*(10)*(10)*(10)*(10)
     ---------------------------------------
     (1.731030946e13)

dan kom ik op 5.776904235e-4 .. dat kan niet bij kansberekeningen .. ben ik nu gewoon dom, ik kom d'r niet uit

[ Voor 71% gewijzigd door GeNiTaLiX op 09-02-2005 14:06 ]

[riezebosch]

Ja, ik weet niet precies hoe je van plan was te bewijzen dat random niet heel erg random is. Maar 10 lijkt me dan vrij weinig. Zelfs in het getal PI zijn denk ik wel reeksen van 10 cijfers die op een gegeven moment terug komen

Het wordt natuurlijk wel interessant als een complete reeks zich blijft herhalen, zoals ik paar posts hierboven heb geprobeerd te omschrijven. Heb zelf even geprobeerd een programmaatje in C++ te maken, maar ben er nog niet uitgekomen. Weet ook niet of dit hetgene is waarmee je kan bewijzen dat computers niet echt random kennen. Daarvoor heb ik me nog te weinig in random verdiept.

[GeNiTaLiX]

jah , maar dat gaat door tot meer dan 2. zoveel biljoen cijfers.. (kwam tot zelfde reeks van max 7 cijfers) weet je toevallig of me kans berekening klopt?

dus de kans van die reeks.. en dan de kans dat deze reeks weer terug komt in de reeks van 1000000.0 getallen -.-

[ Voor 28% gewijzigd door GeNiTaLiX op 09-02-2005 14:39 ]

[riezebosch]

Verwijderd schreef op dinsdag 08 februari 2005 @ 15:30:
[...]

Verder kun je de reeks als bytes naar een file schrijven en deze zippen. Zip zoekt naar herhalende reeksen. Als zip de file kan compressen is hij niet random.

Heb voor de gein even klein testje uitgevoerd met de eerste 17.169.503 decimalen van [url]PI[/url], en prompt wordt ie van 17.512.790 bytes slechts 8.272.737 bytes groot. Dit zou volgens jou betekenen dat de getallen van PI niet random zijn? Toch heeft men hier al eeuwen geen patroon in kunnen ontdekken...

[GeNiTaLiX]

is het niet zo dat omdat in het getal pi dubbele reeksen staan, van bijvoorbeeld 7 cijfers lang of groter, en dat zip de plaatsen aangeeft van deze getallen zodat het bestand gewoon verkleind word, maar pi nog steeds random is.? snap je wat ik bedoel?


15149815211565154165165169544561231516
51651156461653212134566541566535441131231
31315149815315641651656516151651561665165165686
516265166651554566546898479879865
465114615149815

dan hoeft het programma dit getal niet meer te weten , maar alleen de plaats nog aan te geven. dus een soort van "const"

btw, mijn kansberekening?

[ Voor 41% gewijzigd door GeNiTaLiX op 09-02-2005 15:41 ]

[blobber]

Je kunt het ook met statistiek testen:
Test Randomness
maar er is vast wel een site waar een duidelijker voorbeeld instaat, deze is ietwat summier

[ Voor 27% gewijzigd door blobber op 09-02-2005 15:37 ]

[riezebosch]

GeNiTaLiX schreef op woensdag 09 februari 2005 @ 15:31:
is het niet zo dat omdat in het getal pi dubbele reeksen staan, van bijvoorbeeld 7 cijfers lang of groter, en dat zip de plaatsen aangeeft van deze getallen zodat het bestand gewoon verkleind word, maar pi nog steeds random is.? snap je wat ik bedoel?


15149815211565154165165169544561231516
51651156461653212134566541566535441131231
31315149815315641651656516151651561665165165686
516265166651554566546898479879865
465114615149815

dan hoeft het programma dit getal niet meer te weten , maar alleen de plaats nog aan te geven. dus een soort van "const"

btw, mijn kansberekening?

Nou, wat ik probeer aan te geven is dat het ZIP-algoritme niet alleen naar herhalende patronen kijkt. Heb keer module gevolgd waarbij je compressiemethode moest onderzoeken (alleen heb ik toen andere opdracht gedaan), maar uit de presentaties van andere studenten begreep ik dat ze met trees werkten en vaak voorkomende dingen vooraan in de decision-tree zetten waardoor de lengte van de representatie beperkt werd.

En sorry, van kansberekening heb ik geen kaas gegeten (heb Wiskunde-B op HAVO oude stijl gehad).

[GeNiTaLiX]

pff, hoe ga ik nu aantonen dat random bij pascal niet echt random is ik ben desperate..

Door de random formule om te keren ?, het algoritme aan te tonen ?, de cyclus weer te geven?

[EXX]

Volgens mij moet je eens wat meer details gaan vragen mbt de opdracht. Het is allemaal wat vaag zo.

De random generator van pascal is afhankelijk van de compiler en wat voor een algoritme erachter steekt weet alleen de compiler-bouwer.


Wat betreft Turbo Pascal 3.0 heb ik mijn progje eens laten lopen en gezocht maar een herhalende reeks van 30 random numbers na elkaar. Na 2.500.000.000 keer een random getal trekken was er nog geen herhaling gevonden, je kunt er dus van uit gaan dat dit redelijk goede random generatoren zijn.

[GeNiTaLiX]

Ik zou met behulp van een programmeer taal de random formule moeten ontrkrachten, laten zien dat er geen echte random bestaat. De verbanden zoeken. Alleen bij mijn GR heb ik de random formule kunnen ontkrachten.

bijv. Dan met een kansberekening laten zien dat de kans zo klein dat die reeks 2x voorkomt en dat het random niet moet kloppen

[ Voor 25% gewijzigd door GeNiTaLiX op 09-02-2005 16:33 ]

[EXX]

Hoe heb je dat bij je GR bewezen dan?

Random wil zeggen dat het gedrag onvoorspelbaar is. Je kunt alleen uitspraken doen als je grote aantallen gebruikt. Een voorbeeld: je trekt 6 miljoen keer een getal van 1 tot 6 (dobbelsteen als het ware) en kijkt hoeveel keer elk getal voorkomt. Achteraf moet elk getal dus 1 miljoen keer gevallen zijn (met een afwijking van een paar keer). Is er een getal dat beduidend meer/minder voorkomt, is de random generator niet goed random.

[GeNiTaLiX]

Op de gr, is het niet mogelijk zulke grote getallen te nemen het duurt al 10 minuten voor 100000 -.-

code:

0->A
0->B
0->C
While A<aantal
A+1->A
randint(0,1)-B
B+C->C
end
C/aantal

[EXX]

GeNiTaLiX schreef op woensdag 09 februari 2005 @ 16:31:
Alleen bij mijn GR heb ik de random formule kunnen ontkrachten.

Hoe heb je dat dan gedaan?

[GeNiTaLiX]

zoals boven soms kwam het gemiddelde op 0.4 uit

[EXX]

hehe, ben niet zo vertrouwd met GR's, dus ik snap er weinig van

[ Voor 7% gewijzigd door EXX op 09-02-2005 16:53 ]

[riezebosch]

Ik begrijp je redenatie niet dat bij een random-number-generator alle mogelijke getallen evenveel voor moeten komen. Met écht random hoeft dat toch juist helemaal niet, en is toch zelfs dat onvoorspelbaar?

[GeNiTaLiX]

dat moet eigenlijk wel , dat zijn de belangrijkste stukken van een random generator:

- geen herhaling mogelijk (tot na lange tijd dan)
- eerlijke verdeling van getallen
- nog een zal ik zo even opzoeken

(het gaat om een random generator voor de pc dan , je kunt ook met een geigerteller random getallen produceren, maar dat is weer een ander verhaal)

[ Voor 27% gewijzigd door GeNiTaLiX op 09-02-2005 17:04 ]

[Soultaker]

Het hangt er maar vanaf hoe je random definieert, maar voor mij betekent het dat als je 'oneindig' veel getallen genereert, elke eindige string even vaak moet voorkomen als elke andere string van dezelfde lengte.

Je kunt dat controleren door een groot aantal samples te nemen en simpelweg te tellen hoe vaak elke substring voorkomt. Vervolgens kun je uitrekenen of er significante afwijkingen zijn opgetreden.

Het is logisch dat als je 10 bits genereert, een uitkomst als 0000110110 niet significant afwijkt (ook al zijn er 6 0'en en 4 1'en) maar als je 10 letters genereert en je krijgt 'aaabbabba' dan is dat waarschijnlijk al wel significant. Hoe je dat precies moet berekenen hangt van je statistische methode af; zoek maar wat op betrouwbaarheidsintervallen ofzoiets.

[Verwijderd]

Andere page met meer info over hoe je randomness checkt:

http://www.fourmilab.ch/random/

[GeNiTaLiX]

hmm kan iemand die wel selecties kreeg met het random programma, mij die resultaten toesturen (of zeggen welke compiler er is gebruikt) , want de kans dat die herhaling er was is 0.000009999 , dan kan ik die random functie iig ontkrachten en ben ik weer een stap verder

[GeNiTaLiX]

bumbz?

[Verwijderd]

Als je een zinnige uitspraak wil doen moet je toch echt naar statistiek gaan kijken. Zowel Olav (Chi-Square toets) als Blobber (run test) hebben je al methoden gegeven die eenvoudig zijn te implementeren en waarmee je een redelijk onderbouwde uitspraak kan doen. Bij de link van Blobber staat zelfs hoe je de run test kan uitvoeren.

Dus wat wil je nog meer weten? Je moet toch een reden hebben voor je bump.

[GeNiTaLiX]

ik snap dus niet bepaald hoe ik die run test kan uitvoeren

[RobIII]

GeNiTaLiX schreef op donderdag 10 februari 2005 @ 15:16:
ik snap dus niet bepaald hoe ik die run test kan uitvoeren

<zucht>
En wat snap je dan niet? Waar loop je tegen aan? Wat heb je zelf al geprobeerd?

[Verwijderd]

Als je wilt toetsen of je verdeling random is kan je het best uitgaan van een Kolmogorov-Smirnov (K-S) test. Dit is een parametrische toets en zegt meer dan de niet-parametrische Chi-kwadraat.

K-S is niet zo lastig. De idee is dat je een verschilsom berekend door je gegenereerde data te vergelijken met een verwachte verdeling. Een goeie beschrijving vind je hier:
http://www.itl.nist.gov/d...k/eda/section3/eda35f.htm

Wat die verschil score precies betekent lees je vervolgens af uit de tabel hier:
http://www.eridlc.com/onl....appendix&FileName=Table7

[nulkelvin]

riezebosch schreef op woensdag 09 februari 2005 @ 15:17:
[...]


Heb voor de gein even klein testje uitgevoerd met de eerste 17.169.503 decimalen van [url]PI[/url], en prompt wordt ie van 17.512.790 bytes slechts 8.272.737 bytes groot. Dit zou volgens jou betekenen dat de getallen van PI niet random zijn? Toch heeft men hier al eeuwen geen patroon in kunnen ontdekken...

Een byte heeft 2 tot de macht 8 is 256 mogelijkheden om iets op te slaan de 0 tot en met 9 zijn daar 10 van, je hebt dus nog 246 mogelijkheden die je niet gebruikt. Daar haalt zip z'n winst uit.

[Sendy]

Ik lees hier wel een paar vreemde dingen. Ik voel mij genoodzaakt om hierop te reageren...

Soultaker schreef op woensdag 09 februari 2005 @ 17:06:
Het hangt er maar vanaf hoe je random definieert, maar voor mij betekent het dat als je 'oneindig' veel getallen genereert, elke eindige string even vaak moet voorkomen als elke andere string van dezelfde lengte.

"Random" is meestal gedefinieerd als een trekking uit een uniforme verdeling. Dat is een trekking waarbij de kans op een (1) specifieke uitslag gelijk is aan de kans op een andere uitslag. Kijk bijvoorbeeld naar de uniforme steekproef uit [0,1]. De kans op 1/2 is even groot als de kans op (pi)/4. Een gevolg van zo'n steekproef is dat iedere string even vaak voorkomt als iedere ander string (oneindig of niet).

nulkelvin schreef op vrijdag 11 februari 2005 @ 18:35:
Een byte heeft 2 tot de macht 8 is 256 mogelijkheden om iets op te slaan de 0 tot en met 9 zijn daar 10 van, je hebt dus nog 246 mogelijkheden die je niet gebruikt. Daar haalt zip z'n winst uit.

En dit is klinklare onzin. Het zip algoritme (ook wel Huffman codering genoemt) sorteert op de waarden (bytes of words) die het meest voorkomen in het bestand en codeert de waarden die het meest voorkomen met de kleinste codering:
De meeste voorkomende waarde wordt gecodeerd als "00", de een (1) na meest voorkomende waarde wordt "10". De waarden daarna worden "010", "100", "110", etc. Duidelijk is dat de meest voorkomende waarden de minste ruimte inneemt.
Je kan dus ook binaire data coderen, alleen ASCII data zal beter comprimeren.

[en nu niet meer iets schrijven voordat je weet hoe het werkt ]

[swampy]

Welke random is random... mmm

Eens moest ik kiezen uit een aantal personen om een "item" te geven. Dus wat deed ik, ik deed dubbel-random. Dan word er eerst een lijstje gemaakt met random ( in pascal zou dat een array worden ) en dan zou daaruit een trekking gemaakt worden vanaf een "random" getal.

Bijvoorbeeld ik heb een 255 lange array met hexadimale gegevens... dus 0-9+A-F ... en welke wint..dat bepaalt een random tussen 0 en 256

Oftewel random is niet perfect... maar Random^2 kan al aardig helpen.

[.oisyn]

Sendy schreef op vrijdag 11 februari 2005 @ 23:55:
En dit is klinklare onzin.

Nee, hij geeft een argument zonder in detail te treden. Dat jij dat wel doet maakt wat hij zij niet meteen onzin. De winst zit 'm ook gewoon in het feit dat je decimalen codeert in bytes, en daardoor dus heel veel combinaties niet gebruikt.

En bovendien, als de decimalen van pi echt uniform verdeeld zijn, zal elke word combinatie van digits even vaak voorkomen, waardoor elke huffman code vrijwel dezelfde lengte krijgt en de enige winst die er dan nog is is 16 bits vs. het aantal bits in het decimale getal 100 (zoveel combinaties zijn er), oftewel 7. En dat klopt ook wel ongeveer.

[ Voor 50% gewijzigd door .oisyn op 12-02-2005 01:07 ]

[eamelink]

Sendy schreef op vrijdag 11 februari 2005 @ 23:55:
En dit is klinklare onzin. Het zip algoritme (ook wel Huffman codering genoemt) sorteert op de waarden (bytes of words) die het meest voorkomen in het bestand en codeert de waarden die het meest voorkomen met de kleinste codering:
De meeste voorkomende waarde wordt gecodeerd als "00", de een (1) na meest voorkomende waarde wordt "10". De waarden daarna worden "010", "100", "110", etc. Duidelijk is dat de meest voorkomende waarden de minste ruimte inneemt.
Je kan dus ook binaire data coderen, alleen ASCII data zal beter comprimeren.

Ja, maar het ging dus om het comprimeren van pi, en dat gaat je met een huffman écht niet lukken . Omdat hierboven iemand beweerde dat pi niet random zou zijn omdat je het kan zippen, vertelt nulkelvin dat in het geval van het comprimeren van pi met zip, de winst wordt behaald door gebruik te maken van de overige bits in een byte

Dus absoluut geen klinkklare onzin

[en nu niet meer iets schrijven voordat je weet hoe het werkt ]

Lees de draad voordat je blaat

Overigens weet ik een prima manier om pi te comprimeren : "De omtrek van een cirkel gedeeld door zijn diameter". Dan heb je in één keer alle eigenschappen van pi beschreven, dus ook alle decimalen tot in het oneindige Compressiefactor 100%, als je alle decimalen wilt . Maarja, niet echt nuttig in deze context

[.oisyn]

Flauw, dan kun je pi ook wel gewoon comprimeren door het symbool pi te gebruiken ipv z'n decimalen op te schrijven

[Scaror]

PI is natuurlijk ook te comprimeren door een programma (algoritme) te schrijven dat PI produceert. Dan heb je een compressie die niet afhangt van het aantal decimalen van PI, maar toch elke decimaal kan opleveren. PiHex is het eerste wat ik vond met google en heeft een grootte van zo'n 170Kb. Iets meer dan "De omtrek van een cirkel gedeeld door zijn diameter", maar in de complexiteitstheorie kunnen we deze oplossingen als van gelijke orde beschouwen. Met als verschil dat deze oplossing niet 'flauw' is.

[RobIII]

.oisyn schreef op zaterdag 12 februari 2005 @ 00:54:
[...]

Die reply had ik ook in mijn vingers zitten, maar toen ik 'm wou gaan schrijven besefte ik idd opeens dat je inderdaad (decimaal geschreven) je maar 10 (0-9) combinaties uit de ASCII gebruikt, waardoor je er 245 over houdt Misschien een beetje krom, maar daar zou je dus inderdaad je winst uit kunnen halen.(Wat ik dus bedoel is dat je aan 4 bits per digit (0-9) genoeg zou hebben zodat je in 1 byte zowieso 2 digits kwijt zou kunnen). Maar dat hangts dus ook van je "notatie" af (en inderdaad welke compressiemethode).

.oisyn schreef op zaterdag 12 februari 2005 @ 01:08:
Flauw, dan kun je pi ook wel gewoon comprimeren door het symbool pi te gebruiken ipv z'n decimalen op te schrijven

Ultimate compression (99.9999999999...9 %)

Scaror schreef op zaterdag 12 februari 2005 @ 01:34:
PI is natuurlijk ook te comprimeren door een programma (algoritme) te schrijven dat PI produceert. Dan heb je een compressie die niet afhangt van het aantal decimalen van PI, maar toch elke decimaal kan opleveren. PiHex is het eerste wat ik vond met google en heeft een grootte van zo'n 170Kb. Iets meer dan "De omtrek van een cirkel gedeeld door zijn diameter", maar in de complexiteitstheorie kunnen we deze oplossingen als van gelijke orde beschouwen. Met als verschil dat deze oplossing niet 'flauw' is.

Pi kun je echt wel bereken en een programma onder paar Kb (als het al geen paar bytes is?); Die 170Kb dient waarschijnlijk voor een bult runtimes, images, iconen, recourcestrings, het "distributed" gedeelte en andere ongein...170Kb is dan denk ik wel een erg "groot" voorbeeld.
Of het in een paar (k)bytes even snel kan als in PiHex is een tweede.

Anyway, heel deze discussie gaat nergens meer over...

[ Voor 7% gewijzigd door RobIII op 12-02-2005 01:52 ]

[Tomatoman]

In de gegeven codevoorbeelden zo ik zag snel nergens de procedure Randomize() staan. Daarmee creëer je een beginpunt ('seed') voor de Random() functie. In een programma roep je typisch 1x Randomize() aan en daarna een willekeurig aantal keer Random(), net zo vaak als je een random getal wilt hebben. Op veel oudere computers zie je dat als je Randomize() nog niet hebt aangeroepen, de reeks getallen die Random() genereert steeds dezelfde is. Met Randomize() zorg je dat de reeks telkens met een ander getal begint.

Als je op zoek gaat naar patronen in een pseudo-random reeks is het handig om te beginnen met een frequentietabel. Stel dat de functie Random() altijd getallen produceert tussen 0 en 99, bijvoorbeeld met de code

Delphi:

MijnFunctieresultaat := Random(100);

Nu kun je door deze functie heel vaak (minstens 1 miljoen keer) aan te roepen turven hoe vaak het functieresultaat de waarde 0, 1, 2...99 oplevert. Als alle getallen in de frequentietabel niet min of meer even vaak voorkomen, kun je daaruit concluderen dat de reeks niet stochastisch (Engels: random) is. Als alle getallen daarentegen wel ongeveer even vaak voorkomen, kun je daaruit niet concluderen dat de reeks wel stochastisch is - misschien zit er een patroon in dat alle getallen even vaak laat voorkomen.

Een al wat lastigere vorm van een controle of de reeks niet stochastisch is, is de controle of er een cijferreeks in voorkomt die zichzelf vaak herhaalt. Als dat het geval is, is de reeks duidelijk niet stochastisch. Als dat niet het geval is, is het echter nog steeds niet uitgesloten dat de reeks niet stochastisch is. Er zijn immers nog meer patronen denkbaar dan een reeks zich herhalende getallen.

Meer algemeen gezegd is een reeks stochastisch als er geen patroon in aanwezig is. Maar hoe druk je dat in wetenschappelijke termen uit? Dat doe je door middel van de grootheid entropie (Engels: entropy). Hoe groter de entropie van de reeks getallen, des te groter de willekeurigheid daarin. Een reeks volstrekt stochastische getallen zal daardoor de maximale entropie bezitten die een reeks van die lengte kan hebben. Wil je een wetenschappelijk gefundeerde uitspraak doen over de stochasticiteit van een lange reeks getallen, dan zul je de entropie van die reeks moeten berekenen en op basis daarvan een conclusie trekken. Naarmate de entropie lager is, is de kans kleiner dat een reeks getallen stochastisch is. Natuurlijk zal het nooit mogelijk zijn om met 100% zekerheid te concluderen dat een reeks al dan niet stochastisch is, daarvoor heb je namelijk een oneindig lange reeks nodig. Om praktisch toch enkele conclusies te kunnen trekken zul je ergens een grens moeten trekken. Bereken daartoe de kans dat de gegeven reeks getallen niet stochastisch is; als die kans kleiner is dan 0,1% kun je met 99,9% waarschijnlijkheid stellen dat de reeks stochastisch is.

Nog een tip: natuurlijk is het verhaal over entropie niet bepaald eenvoudig. Bedenk echter wel dat een docent erg gevoelig zal zijn voor een poging in de goede richting. Zorg gewoon dat je een paar eenvoudige checks doet om te kijken of je een patroon in een reeks kunt ontdekken (frequentietabel berekenen, herhalende cijferreeksen herkennen). Zo ja, dan is de reeks niet stochastisch ('pseudo-random'). Zo nee, dan is de kan dat de reeks stochastisch is al een stuk kleiner, maar niet uitgesloten. Als je daarna nog een leuk stukje theorie over de betekenis van entropie voor stochastische reeksen schrijft en de software-implementatie achterwege laat - het is geen afstudeeropdracht - kun je gegarandeerd rekenen op een goed cijfer .

[ Voor 7% gewijzigd door Tomatoman op 12-02-2005 19:09 ]

[Scaror]

Pi kun je echt wel bereken en een programma onder paar Kb (als het al geen paar bytes is?); Die 170Kb dient waarschijnlijk voor een bult runtimes, images, iconen, recourcestrings, het "distributed" gedeelte en andere ongein...170Kb is dan denk ik wel een erg "groot" voorbeeld.
Of het in een paar (k)bytes even snel kan als in PiHex is een tweede.

Ja OK, maar daar gaat het niet om. Het gaat erom dat er iets is van vaste (Orde 1) grootte, dat PI voortbrengt. Ik heb gewoon de eerste de beste hit van Google daarvoor gepakt. Of het nu kan in 1MB of in 1KB, het is een vaste grootte.