Periode pseudo random generator

nLight

Ik heb enkele bedenkingen bij de periode van een pseudo-randomgenerator van de vorm

x_(n+1)=(a*x_n + b) mod c met x0 = ...

Eerst dacht ik dat de periode van deze generator gelijk was aan de modulus (c dus).

Dit blijkt niet het geval te zijn indien ik dit uitreken met a = 35, b = 16 en c = 97 (neem x0 = 0).

Dan moest dit wel te maken hebben met onderlinge deelbaarheid of iets dergelijks dacht ik,

maar a,b en c zijn allen onderling ondeelbaar, toch geeft deze randomgenerator maar een periode van 3 aan.

Voor de mensen bekend met maple, hier mijn code :

a:=35

=16:c:=97:x[0]:=0;

> for i from 0 to c do

> x[i+1] := (a*x+b) mod c;

> end do;

Ik krijg dus = 0,16,91,0,16,91,0,16,....

Ik kreeg een bijhorende vraag =

Bepaal een pseudorandomgetallengenerator x_(n+1)=(a*x_n + b) mod c met x_0=d, zodanig dat de periode 1331 is en bovendien 99 <= a <=125 en 110 <= b <= 150 en 1000 <= c <= 1331 en 0 <= d <= 100000.

Maar aangezien ik niet weet wanneer ik een volledige periode heb, kan ik deze vraag ook niet oplossen. Ik weet wel dat de periode niets te maken heeft met de kiem (x0 dus).

Kan iemand helpen?

Mvg,

Yannick

JWvdVeer

De periode heeft volledig te maken met de getallen a, b en c die je kiest. Zelf heb ik hem ook even uitgeschreven in PHP:

Code: Selecteer alles

$iI = 0;

$aiSequence = Array(0);

while(++$iI < 100){

$iA = 35;

$iB = 16;

$iC = 97;

$aiSequence[] = ((($iA * $aiSequence[$iI - 1]) + $iB) % $iC);

}

print_r($aiSequence);

Je kunt de opdracht die jij krijgt ook gewoon uitprogrammeren en dan steeds de eerste 1332 termen uit laten rekenen en zo gauw een term eerder voorkomt (ofwel, de eerste term gelijk is aan de berekende term), overgaan op de volgende.

Ik vrees dat we met een zogenaamd wiskundige aanpak in deze niet heel ver gaan komen, omdat je met modulo werkt. En module heeft de nogal vervelende eigenschap dat wiskundige functies daarmee niet goed te differentiëren of integreren zijn (punten waarop de differentiaal gewoon niet bestaat, dus vervolgens is de integraal ook onbekend).

nLight

Met PHP ben ik niet bekent, maar je bedoelt dus dat er geen verband is tussen die getallen

en dat ik het best het 'uitprobeer' door te programmeren?

Ik vind dit nogal raar, want ik kreeg dit zinnetje nog bij de vraag :

Bepaal een pseudorandomgetallengenerator x_(n+1)=(a*x_n + b) mod c met x_0=d, zodanig dat de periode 1331 is en bovendien 99 <= a <=125 en 110 <= b <= 150 en 1000 <= c <= 1331 en 0 <= d <= 100000. Deze zoektocht mag niet langer dan 1 minuut duren; anders heb je niet goed genoeg nagedacht...

Blijkbaar zit er toch iets meer achter?

Alvast bedankt,

Yannick

JWvdVeer

Deze zoektocht mag niet langer dan 1 minuut duren; anders heb je niet goed genoeg nagedacht...

Bij mij duurt deze zoektocht om een indicatie te geven 92 seconden. En ik heb dan 111 combinaties van a, b en c bij een d van 0 die aan alle voorwaarden voldoen. Als ik slechts één combinatie wil hebben, ben ik in minder dan een halve seconde klaar.

En ja, ik heb er heel even over nagedacht ](*,)

Maar mocht jij een wiskundige aanpak zien, dan hoor ik het graag

Rogier

nLight schreef:Met PHP ben ik niet bekent, maar je bedoelt dus dat er geen verband is tussen die getallen

en dat ik het best het 'uitprobeer' door te programmeren?

Ik vind dit nogal raar, want ik kreeg dit zinnetje nog bij de vraag :

Bepaal een pseudorandomgetallengenerator x_(n+1)=(a*x_n + b) mod c met x_0=d, zodanig dat de periode 1331 is en bovendien 99 <= a <=125 en 110 <= b <= 150 en 1000 <= c <= 1331 en 0 <= d <= 100000. Deze zoektocht mag niet langer dan 1 minuut duren; anders heb je niet goed genoeg nagedacht...

Tip: 1331=11³

nLight

Uhm.. ik zie het verband echt niet. Hoe zou 11^3 mij kunnen helpen? De kiem maakt niet uit, dus neem ik al gemakkelijkheidshalve 0 voor, maar verder dan dat geraak ik ook echt niet. Nog een tip zou handig zijn.

Yannick

Rogier

Waar het om gaat is dat de getallen niet tussentijds al een c-voud worden. Wat zou er gebeuren als je bijvoorbeeld a=11²+1 neemt en b geen 11-voud..?

JWvdVeer

Waar het om gaat is dat de getallen niet tussentijds al een c-voud worden. Wat zou er gebeuren als je bijvoorbeeld a=11²+1 neemt en b geen 11-voud..?

Hoe kwam jij hier op? Want het gegeven wat je geeft klopt heel goed met mijn resultaten:

(...)

string 'Voldoet voor: A = 122, B = 111 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 112 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 113 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 114 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 115 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 116 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 117 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 118 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 119 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 120 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 122 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 123 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 124 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 125 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 126 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 127 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 128 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 129 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 130 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 131 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 133 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 134 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 135 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 136 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 137 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 138 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 139 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 140 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 141 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 142 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 144 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 145 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 146 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 147 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 148 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 149 en C = 1331' (length=42)

string 'Voldoet voor: A = 122, B = 150 en C = 1331' (length=42)

Ofwel: A = 11² + 1 en de elfvouden missen bij de B.

Waar het om gaat is dat de getallen niet tussentijds al een c-voud worden.

Je gaat al bij voorbaat uit van een C van 1331... Hoezo?

nLight

Waar het om gaat is dat de getallen niet tussentijds al een c-voud worden. Wat zou er gebeuren als je bijvoorbeeld a=11²+1 neemt en b geen 11-voud..?

Dan zal na een paar keren de (a*x + b) deelbaar worden door c (11^3) en dus geen volledige periode geven...

Hoe zit het dan met die eerste oefening? 97 is namenlijk een priemgetal..

nLight

Vergeet wat ik hierboven zei, slaagt op niet veel...

Bedankt voor de tips maar ik geraak er nog echt niet aan uit.

EvilBro

Is dit een project Euler vraag?

JWvdVeer

Het antwoord heeft Rogier eigenlijk al min of meer gegeven, kies A zo dat geldt:

\(A = 11n + 1, n \in \mathbb{Z}\)

En kies daarbij een B waarvan geldt:

\(B \neq 11n, n \in \mathbb{Z}\)

Kies voor C 1331.

Maar de reden waarom dat is, zou ik graag nog willen horen van Rogier.

nLight

Ja, ik ook. En wat is dan de reden dat ik maar periode 3 krijg bij mijn eerste oefening?

JWvdVeer

Ja, ik ook. En wat is dan de reden dat ik maar periode 3 krijg bij mijn eerste oefening?

\((a(a(0a + b) + b) + b) = (35(35(0 + 16) + 16) + 16) = 20176 \longrightarrow \frac{20176}{97} = 208\)

\( \longrightarrow (a(a(0a + b) + b) + b)\,\%\,c = ((a((a((0a + b)\,\%\,c) + b)\,\%\,c) + b)\,\%\,c) = 0\)

Waarbij geldt:

\(x\,\%\,y := x - y\left\lfloor \frac{x}{y}\right\rfloor, y \in \mathbb{R^+}\)

.

Voor vier van die termen is zoiets nog wel te doen. Maar als je zoiets voor 1331 termen uit moet gaan schrijven, dan heb je een probleem.

Rogier

Dan zal na een paar keren de (a*x + b) deelbaar worden door c (11^3) en dus geen volledige periode geven...

Juist niet! Even simpel gezegd: als a=11²+1 dan zal die 11² zorgen voor een factor die binnen 11 keer alweer rondgaat (omdat je modulo 11³ rekent kun je dat deel dus negeren) en die +1 extra doorloopt de volledige periode.

Als a overigens een 11-voud plus 1 is (dus a=12, a=23, enz) zou dat om dezelfde reden ook al voldoen (het 11-voud gaat dan binnen 121 keer rond en de resterende +1 in a zorgt voor een volledige periode).

Je gaat al bij voorbaat uit van een C van 1331... Hoezo?

C mag maximaal 1331 zijn. Hoe had je met een kleinere C een periode van 1331 willen krijgen? ](*,)

Hoe zit het dan met die eerste oefening? 97 is namenlijk een priemgetal..

Er zijn wat ingewikkelde restricties waaraan a,b,c moeten voldoen, wil je een randomgenerator met volledige periode verkrijgen. Het begingetal x0 maakt daarbij overigens niet uit.

Zie wikipedia al is die definitie volgens mij niet correct. (wel een interessant probleem trouwens, ik kijk binnenkort nog wel een keer wat de restricties dan wel precies zijn)

Met c=97 gaat het in ieder geval niet lukken (voor geen enkel priemgetal c overigens). Met bijvoorbeeld c=96 wel, neem voor a een 12-voud plus 1 (dus a=13, a=25, enz) en b geen 2- of 3-voud (dus b=1,5,7,enz). Met c=98 kan het ook, a moet dan een oneven 7-voud plus 1 zijn (a=15, a=29, enz) en b geen 2- of 7-voud (b=1,3,5,9,11,enz).

Wetenschapsforum

Laatste berichten

Nieuwsberichten

Periode pseudo random generator

Periode pseudo random generator

Re: Periode pseudo random generator

Re: Periode pseudo random generator

Re: Periode pseudo random generator

Re: Periode pseudo random generator

Re: Periode pseudo random generator

Re: Periode pseudo random generator

Re: Periode pseudo random generator

Re: Periode pseudo random generator

Re: Periode pseudo random generator

Re: Periode pseudo random generator

Re: Periode pseudo random generator

Re: Periode pseudo random generator

Re: Periode pseudo random generator

Re: Periode pseudo random generator