Lgraczyk: /* Zadanie */

2017-03-27T06:32:08Z

Zadanie

← Older revision		Revision as of 06:32, 27 March 2017
Line 18:		Line 18:
	* <code>c</code> i <code>m</code> nie maja wspolnych dzielników,		* <code>c</code> i <code>m</code> nie maja wspolnych dzielników,
	* <code>b = g-1</code> jest wielokrotnoscia kazdej liczby pierwszej <code>p</code>, ktora jest dzielnikiem liczby <code>m</code>,		* <code>b = g-1</code> jest wielokrotnoscia kazdej liczby pierwszej <code>p</code>, ktora jest dzielnikiem liczby <code>m</code>,
-	* <code>b</code> jest wielokrotnością 4 jesli <code>n</code> ~~tez~~ jest wielokrotnością 4.	+	* <code>b</code> jest wielokrotnością 4 jesli <code>n</code> też jest wielokrotnością 4.

	Dla uproszczenia należy przyjąć <code>c = 0</code>, otrzymując w ten sposób multiplikatywny liniowy generator kongruentny (MLCG).		Dla uproszczenia należy przyjąć <code>c = 0</code>, otrzymując w ten sposób multiplikatywny liniowy generator kongruentny (MLCG).
Line 68:		Line 68:
	** standardowego generatora ROOT'a <code>gRandom->Rndm(1)</code>.		** standardowego generatora ROOT'a <code>gRandom->Rndm(1)</code>.
	* Narysować na jednym wykresie histogram (odpowiednio unormowany) oraz funkcję teoretyczną <code>f(x)</code> (obiekt <code>TF1</code>). (1 pkt.)		* Narysować na jednym wykresie histogram (odpowiednio unormowany) oraz funkcję teoretyczną <code>f(x)</code> (obiekt <code>TF1</code>). (1 pkt.)
-

	== Uwagi ==		== Uwagi ==

Lgraczyk: Created page with "{| align="right" | TOC |} == Zadanie == ''Część pierwsza'': '''liniowy kongruentny generator liczb losowych''' (1 pkt.) Należy napisać generator liczb pseudolosowych..."

2017-03-27T06:31:02Z

Created page with "{| align="right" | __TOC__ |} == Zadanie == ''Część pierwsza'': '''liniowy kongruentny generator liczb losowych''' (1 pkt.) Należy napisać generator liczb pseudolosowych..."

New page

{| align="right"
| __TOC__
|}

== Zadanie ==

''Część pierwsza'': '''liniowy kongruentny generator liczb losowych''' (1 pkt.)

Należy napisać generator liczb pseudolosowych oraz zapisać wygenerowane liczby do pliku.

Stworzony generator powinien opierać się na wzorze:

<code>x[j+1] = (g*x[j] + c) mod m.</code>

Generator taki nazywamy generatorem LCG - czyli generatorem liniowym kongruentnym. Zadanie pewnej wartości poczatkowej <code>x[0]</code> definiuje nam zatem cały ciąg, który ponadto jest ciągiem okresowym. Okres zależy od doboru parametrów i przy spelnieniu kilku warunków osiąga maksymalnie wartość <code>m</code>. Warunki te to:

* <code>c</code> i <code>m</code> nie maja wspolnych dzielników,
* <code>b = g-1</code> jest wielokrotnoscia kazdej liczby pierwszej <code>p</code>, ktora jest dzielnikiem liczby <code>m</code>,
* <code>b</code> jest wielokrotnością 4 jesli <code>n</code> tez jest wielokrotnością 4.

Dla uproszczenia należy przyjąć <code>c = 0</code>, otrzymując w ten sposób multiplikatywny liniowy generator kongruentny (MLCG).

* Wartości <code>g</code> oraz <code>m</code> powinny być łatwe do modyfikacji w programie.

Efektem działania makra powinien być plik nazwa.dat zawierający ciąg wygenerowanych liczb dla zadanych parametrów. Makro należy uruchomić trzy razy, otrzymując trzy pliki: <code>losowe1.dat, losowe2.dat, losowe3.dat</code>, dla parametrów odpowiednio:

* <code>m=97</code> i <code>g=23</code>,
* <code>m=32363</code> i <code>g=157</code>,
* <code>m=147483647</code> i <code>g=16807</code>.

''Część druga'': '''test widmowy''' (1 pkt.)

Należy przeprowadzić test widmowy aby przetestować jakość generatora. By to zrobić należy narysować na płaszczyźnie punkty o współrzędnych <code>(x[n], x[n+1])</code>. Uzyskany obraz utworzy wzór przypominający widmo generatora - stąd nazwa testu.

Jeśli punkty będą rozłożone równomiernie generator można uznać za dobry. Jeśli zdecydowanie widać pewną okresowość - punkty powtarzają się wielokrotnie - generator nie działa poprawnie. Oczywiście na rozłożenie punktów wpływa jedynie dobór parametrów <code>g</code> i <code>m</code>.

* Do tworzenia wykresów widma poleca się użycie obiektów <code>TH2D</code>.

Wynikiem powinny być trzy wykresy widma.

''Część trzecia'': '''generacja liczb losowych oparta na transformacji rozkładu jednorodnego''' (3 pkt.)

Dowolna funkcja zmiennej losowej jest zmienną losową. Powstaje więc pytanie jaka jest gęstość zmiennej losowej Y jeżeli znana jest gęstość <code>f(x)</code>. Zakładamy, że prawdopodobieństwo <code>g(y)dy</code> jest równe <code>f(x)dx</code>, gdzie <code>dx</code> odpowiada wartością <code>dy</code>. Warunek jest spełniony dla odpowiednio małych <code>dx</code>. Wynika stąd, że:

<code>g(y) = dx/dy f(x)</code>

Teraz jeżeli założymy, że gęstość prawdopodobieństwa <code>f(x)</code> wynosi 1 w <code>0<=x<=1</code> i <code>f(x) = 0</code> dla <code>x<= 0 i x>1</code> to powyższe równanie możemy zapisać w postaci:

<code>g(y)dy = dx = dG(y),</code>

gdzie <code>G(y)</code> jest dystrybuantą zmiennej losowej <code>Y</code>. Co po całkowaniu daje nam

<code>x = G(y) => y = G^-1(x).</code>

Jeśli zmienna losowa <code>X</code> ma rozkład jednostajny na odcinku pomiędzy 0 i 1 oraz jeśli znana jest funkcja odwrotna <code>G^-1(x)</code> to funkcja <code>g(y)</code> opisuje gęstość prawdopodobieństwa rozkładu zmiennej losowej Y.

Używając tej metody należy wygenerować 10000 liczb z rozkładu:

[[File:Lab06_wzor.png]]

Dla <code>tau = 2</code>:

* Należy wygenerować 10000 liczb z rozkładu 0 do 1 używając generatora z części pierwszej.
* Analitycznie (na kartce) policzyć dystrybuantę tego rozkładu, a następnie funkcję odwrotną. (1 pkt.)
* Wygenerować rozkład <code>f(x)</code> - wrzucając wygenerowane wartości do histogramu - korzystając z: (1 pkt.)
** liczb wygenerowanych wcześniej i wczytanych z plików <code>losowe1.dat, losowe2.dat, losowe3.dat</code>,
** standardowego generatora ROOT'a <code>gRandom->Rndm(1)</code>.
* Narysować na jednym wykresie histogram (odpowiednio unormowany) oraz funkcję teoretyczną <code>f(x)</code> (obiekt <code>TF1</code>). (1 pkt.)

== Uwagi ==
* Wczytywanie danych z pliku:
ifstream ifile;
ifile.open("dane.dat");
double val;
while(ifile>>val)
{
cout<<val<<endl;
}
ifile.close();

* Zapisywanie danych do pliku:
ofstream ofile;
ofile.open("dane.dat");
for(int i=0;i<N;i++)
ofile<<val<<endl;
}
ofile.close();

== Wynik ==
Przykładowy rozkład dla parametrów:
* <code>m=97, g=23</code>
[[File:lab06_n97_g23_2.png]]
* <code>m=2147483647, g=16807</code>
[[File:lab06_n2147483647_g16807_2.png]]

Przykładowy wynik transformacji rozkładu jednorodnego:

[[File:lab06_b_2.png]]

KADD 2017 Zadanie 6 - Revision history

Lgraczyk: /* Zadanie */

Lgraczyk: Created page with "{| align="right" | __TOC__ |} == Zadanie == ''Część pierwsza'': '''liniowy kongruentny generator liczb losowych''' (1 pkt.) Należy napisać generator liczb pseudolosowych..."

Lgraczyk: Created page with "{| align="right" | TOC |} == Zadanie == ''Część pierwsza'': '''liniowy kongruentny generator liczb losowych''' (1 pkt.) Należy napisać generator liczb pseudolosowych..."