01_RND

1. Algoritmi i Strukture Podataka

Generatori
pseudoslučajnih brojeva

2. Generatori pseudoslučajnih brojeva

• Generator slučajnih brojeva: meri fizičku veličinu
za koju se pretpostavlja da je slučajne prirode
• Generator pseudoslučajnih brojeva: koristi neki algoritam
(najčešće baziran na celobrojnoj aritmetici)
• Pseudo = nije pravi: bazira se na algoritmu determinizam
• Realizacija: hardverska ili softverska
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
2

3. Generatori pseudoslučajnih brojeva

• Kvalitetan generator pseudoslučajnih brojeva
– dobre statističke karakteristike (uniformna raspodela generisanih
brojeva)
– velika perioda ponavljanja sekvence
• Primena
– simulacije realnih sistema (Monte-Carlo metode)
– kriptografija
– statističke analize
– sastavni su deo generatora pseudoslučajnih brojeva po drugim
raspodelama
– Bibliotečke funkcije jezika C
– rand() i srand() : loših karakteristika,
prihvatljivih samo za nebitne primene (video-igre)
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
3

4. Generatori pseudoslučajnih brojeva - LKG

• Linearan kongruentan generator (LKG) periode m
X n 1 (a X n c) mod m
0 m : moduo
0 a m : množilac
0 c m : inkrement
0 X 0 m : "klica" (eng. seed )
• (Donald Knuth) Perioda je m ako :
– c i m su uzajamno prosti
– a-1 je deljivo svim prostim činiocima m
– a-1 je umnožak 4 ako je m umnožak 4
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
4

5. Generatori pseudoslučajnih brojeva - LKG

• Predložene kombinacije (32-bitni računar, m=2 32)
– a = 429493445, c = 907633385 (Knuth)
– a = 1664525, c = 1013904223 (Numerical Recipes in C)
• Kod (vraća realan broj od 0 do 1):
unsigned long u;
unsigned long iurng() {
return u = 429493445 * u + 907633385;
}
void setSeed(unsigned long seed) {
u = seed;
}
double randomD() {
return (iurng() / 4294967296.);
}
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
5

6. Poređenje: 100 000 tačaka (parovi X i Y)

Bibliotečka funkcija rand
Visual C++ 2008
Elektrotehnički fakultet,
Beograd
LKG (Knuth)
Algoritmi i Strukture Podataka
6

7. Generatori pseudoslučajnih brojeva - BBS

• Blum Blum Shub
Xn+1 = (Xn)2 mod M, gde je M=p*q,
p i q su prosti brojevi kongruentni sa 3 po modulu 4
– Nakon svake iteracije uzima se nekoliko bita Xn
kao deo rezultata (potrebno je više iteracija da bi se dobio jedan
pseudoslučajni broj)
• Generator je relativno spor (u odnosu na druge metode)
• Odlične karakteristike za kriptografiju, ne i za simulacije
(zbog sporosti)
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
7

8. Generatori pseudoslučajnih brojeva - BBS

• Primer: p=11, q=19, X0=3, M=p*q=209.
=> X1=9, X2=81, X3=82, X4=36, X5=42, X6=92...
• Uzimamo npr. samo bit (parne) parnosti (eng. parity bit)
svakog člana, pa je generisana sekvenca: 011010...
• Ako uzmemo najniži bit generisana sekvenca: 110000...
• Ove i slične sekvence se mogu kombinovati da se dobije
pseudoslučajni broj
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
8

9. Generatori pseudoslučajnih brojeva - FGK

• Fibonačijev generator sa kašnjenjem
(eng. Lagged Fibonacci generator - LFG)
– Koristi način određivanja Fibonačijevih brojeva kao ideju:
Fn = Fn-1 + Fn-2
S n ( S n j op S n k ) mod m, 0 j k
op je neka operacija (+ - * / xor)
• perioda zavisi od odabrane operacije
• j i k ne mogu da se biraju proizvoljno
(postoji objavljen spisak)
• problematična inicijalizacija (zavisno od vrednosti j i k)
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
9

10. Zadatak 1 – (SI) K1, mart 2020.

• Neka je data funkcija random() koja vraća broj 0 ili 1 sa
podjednakom verovatnoćom. Objasniti kako bi se
korišćenjem zadate funkcije implementirala funkcija koja
vraća vrednost 0 sa verovatnoćom 25%, a 1 sa
verovatnoćom od 75%.
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
10

11. Zadatak 1 – rešenje

• Umesto dva ishoda, potrebna su nam četiri ishoda, kako
bi ispunili zadate verovatnoće
• To sugeriše da je potrebno dva puta pozvati random()
funkciju
• Kombinacija 00 može da se tumači kao vrednost 0, a
ostale (01, 10 i 11) kao vrednost 1
• Optimizacija:
Možemo primetiti da ako prvi poziv generiše broj 1, da
drugi poziv nije neophodan (jer znamo da daje ishod 1)
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
11

12. Zadatak 2

• Koristeći LKG generator implementirati funkciju coin()
koja sa približno jednakom verovatnoćom vraća
vrednosti 0 ili 1. Koristeći funkciju coin() implementirati
funkciju cube() koja simulira bacanje kocke, tj. vraća
vrednost od 1 do 6 sa približno podjednakim
verovatnoćama.
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
12

13.

void initCoin(unsigned long seed)
{
setSeed(seed); //svodi se na inicijalizaciju LKG
}
int coin()
{
double i = randomD();
if (i < 0.5)
return 0;
else
return 1;
}
// ideja je da slučajno generišemo
// svaki bit
int cube()
{
int i = coin();
i = i * 2 + coin();
i = i * 2 + coin();
if (i >= 6) return cube();
// ponovo pozovemo funkciju
// ako je rezultat veći nego
// što treba
else return i + 1;
}
U test programu, u 60.000 poziva funkcije cube(), povratna vrednost iznosila je:
1 – 9.989 puta
4 – 9.972 puta
2 – 10.000 puta
5 – 9.924 puta
3 – 10.047 puta
6 – 10.068 puta
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
13

14. Zadatak 3 – (SI) K1, mart 2017.

• Neka je u nekom programskom jeziku dostupna funkcija
za generisanje pseudoslučajnih brojeva rand7 koja vraća
ceo broj uniformne raspodele u opsegu od 0 do 7.
Korišćenjem funkcije rand7 napisati u pseudokodu
funkciju rand5 koja vraća ceo broj u opsegu od 0 do 5 sa
istim karakteristikama. Obrazložiti odgovor.
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
14

15. Zadatak 3 – rešenje

• Ako probamo rezultat rand7 da „sažmemo“ u opseg od 0 do 5
deljenjem, dobijamo neuniformnu raspodelu
• Rešenje:
– pozovemo rand7 i ako dobijemo broj van opsega, ponovo pozovemo
funkciju rand7
– rand7 je uniformna, tako da će i rand5 onda biti uniformna
int rand5()
{
int item;
while ( (item = rand7()) > 5);
return item;
}
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
15

16. Zadatak 4

• Napisati program koji izračunava približnu vrednost
broja π primenom generatora slučajnih brojeva.
R=1
Elektrotehnički fakultet,
Beograd
Ideja:
• Generisati slučajne brojeve kao
koordinate tačaka u ravni
(u prvom kvadrantu)
• Odnos broja tačaka u kvadratu
jedinične dužine stranica
i četvrtini kružnice
jediničnog poluprečnika
daje traženu (približnu) vrednost.
Algoritmi i Strukture Podataka
16

17. Zadatak 4 – rešenje Python / C

import random
#include <stdio.h>
#include <stdlib.h>
def pi(i):
u_krugu = 0
for j in range(i):
# random.random() -> [0,1)
x = random.random()
y = random.random()
if x * x + y * y <= 1.0:
u_krugu += 1
return 4.0 * u_krugu / i
if __name__ == "__main__":
j = 1
for iteration in range(7):
j = j * 10
pi_approx = pi(j)
print(f"{pi_approx:.6f}")
Elektrotehnički fakultet,
Beograd
double pi(int i) {
double x, y;
int u_krugu = 0, j;
for (j = 0; j < i; j++) {
x = (double)rand()/(RAND_MAX + 1.0);
y = (double)rand()/(RAND_MAX + 1.0);
if (x * x + y * y <= 1.0)
u_krugu++;
}
return 4.0 * u_krugu / i;
}
int main() {
int i, j = 1;
for (i = 0; i < 7; i++) {
j = j * 10;
printf("%.6f ",pi(j));
}
return 0;
}
Algoritmi i Strukture Podataka
17

18. Zadatak 4 – rešenje

Napomena:
• Python modul random daje podršku za nekoliko različitih
funkcija za generisanje pseudoslučajnih brojeva; ovde je
odabrana ona koja vraća realan broj u opsegu [0, 1)
• C biblioteka stdlib.h sadrži funkciju rand() koja vraća ceo
broj u opsegu [0, RAND_MAX], gde je RAND_MAX takođe
definisano u toj biblioteci
Rezultati:
Broj tačaka
Python [3.12]
C [gnu 11.4.0]
Elektrotehnički fakultet,
Beograd
10
3.128
3.184
100
3.1153
3.1336
1000
3.13512
3.14208
10000
3.141368
3.143036
100000
3.141651
3.142280
1000000
3.141492
3.141713
10000000
3.141566
3.141589
18