AANSLUITINGSPROJECT TUE - VO
startpagina ] omhoog ] rekenen met resten ] lcgenerator ] roostertoets ] [ beterelcmgenerator ]

 

Een (betere) random-getallengenerator

Als m groter wordt dan kun je een rij met een langere cyclus krijgen. In de tabel hieronder zie je het begin van de rij die hoort bij.

xn+1= 17xn  + 11 (mod 1000)
x0 = 1

x0 x1 x2 x3 x4 x5 x6 x7 x8 x9
1 28 487 290 941 8 147 510 681 588

Deze rij lijkt vrij springerig te zijn. Zou hij een cyclus met maximale lengte, die is 1000, hebben? Het antwoord op die vraag is nee. Met een programma kun je nagaan dat x200 =1. 

Die 200 getallen zijn overigens zeer goed verdeeld over {0 , 1, 2 ... 999} Dat zie je goed in de onderstaande grafiek. In die grafiek is elk getal uit de rij gedeeld door 1000 en vervolgens afgerond op 1 decimaal. Op die manier krijg je willekeurige getallen tussen 0 en 1 (met 1 decimaal)

Een langere rij krijg je als je a = 1 kiest:

xn+1= xn  + 11 (mod 1000)
x0 = 1

Je krijgt dan 1000 verschillende getallen. Als je die getallen door 1000 deelt en naar beneden afrondt dan krijg je natuurlijk 100 keer 0, 100 keer 1... en 100 keer 0,9. Helaas is het patroon dit keer zeer regelmatig. De streepjes in de onderstaande grafiek zijn steeds 10 opeenvolgende waarden uit de rij.

Het mooist zouden waarden zijn die een "springerige" rij met 1000 verschillende getallen leveren. Dat betekent experimenteren met a en b:

opgave 7 
De bovenstaande grafieken zijn gemaakt met behulp van het bestand random.xls.

a) Download en open dat bestand, lees de handleiding en bekijk de werkbladen met de gegevens, berekeningen en grafieken.

downloaden random.zip

b) Maak een (op het oog) springerige rij met cycluslengte 1000 leveren.
c) Maak ook een (op het oog) springerige rij met cycluslengte 1100 leveren.

Er is natuurlijk veel onderzoek gedaan naar goede keuzen voor a, b en  m en men heeft gevonden dat goede kandidaten voldoen aan:

  1. b en m hebben geen gemeenschappelijke factoren
  2. (a-1) is een veelvoud van elk priemgetal  in de ontbinding van m  (link: wat is een priemgetal?) 
  3. (a-1) is een geheel veelvoud van 4 als m een geheel veelvoud van 4 is 

Voldoet de bovenste rij op deze pagina aan deze voorwaarde?:

voorwaarde 1: klopt 
b = 11 is een priemgetal en 1000 is geen veelvoud van 11
voorwaarde 2: klopt NIET 
1000 = 2*2*2*5*5*5, de priemfactoren in 1000 zijn dus 2 en 5 maar (a - 1) = 17 - 1 = 16  is geen veelvoud van 5
voorwaarde 3: klopt
m = 1000 is een veelvoud van 4 en  a - 1 = 16  = 4*4 

opgave 8
a) Voldoen de rijen die je in opgave 7 gemaakt hebt aan deze voorwaarden?
b) Bepaal drie verschillende waarden van a  (b = 11 en m = 1000) zodat aan alle voorwaarden voldaan is.
c) Onderzoek met random.xls of de cycluslengte van die rijen 1000 is?

Als een rij voldoet aan de drie voorwaarden dan wil dat nog niet zeggen dat de rij "goed" is. Er bestaan verschillende testen waarmee men de mate van randomness kan testen. Een van die testen heet de roostertoets. Meer informatie daarover vind je op de pagina: roostertoets