Klasa III: liczby pseudolosowe

Liczba losowa (ang. random number) jest liczbą r należącą do pewnego zbioru wartości {r₁, ..., r_n}, której konkretna wartość jest przypadkowa i nie można jej dokładnie przewidzieć. Takie liczby mają ogromne zastosowanie we wszelkiego rodzaju symulacjach i grach losowych. Przykładem liczby losowej jest np. wynik rzutu kostką - może wypaść od 1 do 6 oczek, jednakże jeśli kostka nie jest oszukana, to każda z tych liczb jest tak samo prawdopodobna i przed dokonaniem rzutu wynik nie może być poznany.

Problem z otrzymaniem liczb losowych wynika stąd, iż komputer jest maszyną, której operacje są ściśle określone i nie ma możliwości wygenerowania liczby o nieokreślonej wartości. Gdy człowiek dokonuje rzutu kostką, nie wie co wypadnie. Taka sama operacja na komputerze wymagałaby działania, którego wynik jest nieprzewidywalny – żadna z operacji wykonywanych przez procesor nie posiada takiej cechy (o ile procesor jest sprawny). Problem starano się rozwiązać wykorzystując zewnętrzne źródła sygnałów losowych (np. generatory białego szumu ), jednakże w tego typu urządzenia nie są standardowo wyposażano komputery osobiste – należałoby wspomnieć o próbach wykorzystania szumów kart dźwiękowych, jednakże system ten nie rozpowszechnił się z prostej przyczyny – różne karty dźwiękowe szumią różnie, a te z górnej półki nie szumią praktycznie wcale.

Obecnie możemy skorzystać z serwisów internetowych, które udostępniają nam liczby losowe z wybranego zakresu, na przykład witryna:

https://www.random.org/

W witrynie dostępny jest prosty interfejs generatora liczb losowych:

W okienku ustawiamy pożądany zakres liczb losowych, po czym klikamy w przycisk Generate. Wylosowana liczba losowa jest wyświetlana w polu Result. Tego typu rozwiązanie pozwala nam losować pojedyncze liczby.

Liczby losowe używane są powszechnie przy programowaniu komputerów – wszelkiego rodzaju gry losowe, symulacje różnych procesów losowych, statystycznych, testowanie algorytmów dla losowych zestawów danych itp. Ponieważ nie możemy w prosty sposób mieć prawdziwych liczb losowych, musimy się zadowolić ich sztucznym odpowiednikiem – liczbami pseudolosowymi (ang. pseudorandom numbers). Liczby pseudolosowe wyglądają jak losowe, lecz tworzy się je algorytmicznie. Oznacza to, iż znając wzór generacyjny oraz kilka kolejnych liczb pseudolosowych możemy bez problemu wygenerować wszystkie dalsze – tej cechy nie posiadają prawdziwe liczby losowe, w przeciwnym razie totolotek straciłby sens a kasyna zbankrutowałyby.

Do zapamiętania:

Liczba losowa.
Dlaczego liczby losowej nie można normalnie uzyskać na komputerze?
Liczba pseudolosowa: czym różni się od prawdziwej liczby losowej?

do podrozdziału do strony

Do rozwiązania problemu generacji liczb pseudolosowych opracowano specjalne funkcje modularne zwane liniowymi generatorami kongruencyjnymi liczb pseudolosowych (ang. pseudorandom number linear congruential generator – w skrócie LCG) o następującej postaci:

X_n = (a×X_n-1+c)%m
X_n	– n-ta liczba pseudolosowa
X_n-1	– poprzednia liczba pseudolosowa
a	– mnożnik
c	– przyrost
m	– moduł

Ze wzoru wynika, iż kolejna liczba pseudolosowa X_n powstaje z poprzedniej X_n-1. Liczby te tworzą zatem ściśle określony ciąg kolejno następujących po sobie wartości.

Drugą cechą charakterystyczną jest to, iż liczba pseudolosowa X_n jest resztą z dzielenia przez moduł m. Skoro tak, to może tylko przyjmować wartości od 0 do m-1. Z pierwszej i drugiej własności wynika, iż po m cyklach obliczeniowych, liczby pseudolosowe zaczynają się powtarzać w tej samej kolejności.

Jeśli współczynniki a, c i m są źle dobrane, to okres powtarzania może być krótszy niż m.

Rozróżniamy dwa podstawowe rodzaje generatorów LCG:

Addytywny LCG:	X_n = (aX_n-1+c)%m
Multiplikatywny LCG:	X_n = aX_n-1%m

Podstawowa różnica pomiędzy nimi jest taka, iż generator addytywny LCG może generować liczby pseudolosowe z zakresu od 0 do m-1, a generator multiplikatywny generuje je z zakresu od 1 do m-1. Poniżej podajemy prosty algorytm doboru współczynników dla generatora LCG.

Określamy zakres liczb pseudolosowych 0...X_max (dla LCG multiplikatywnego jest to 1...X_max). Moduł m jest zawsze o 1 większy od maksymalnej liczby w zakresie, czyli:

m = X_max+1

Przyrost c musi być względnie pierwszy z modułem m. Możemy m rozłożyć na czynniki pierwsze i dla c wybieramy czynniki nie występujące w m. Możemy również generować pseudolosowe c i sprawdzać, czy spełnia warunek:

NWD(c, m) = 1

Mnożnik dobieramy wykorzystując regułę, iż wyrażenie a-1 jest podzielne przez każdy czynnik pierwszy modułu m. Jeśli moduł m dzieli się przez 4, to a-1 również powinno być podzielne przez 4.

Przykład:

Zaprojektować addytywny generator LCG generujący liczby pseudolosowe w przedziale od 0 do 11.

Z warunków zadania mamy:

X_max = 11
m = X_max + 1 = 11 + 1 = 12

Przyrost c musi być względnie pierwszy z m. Moduł m rozkładamy na iloczyn czynników pierwszych:

m = 2 × 2 × 3

Na przyrost c możemy wybrać dowolną liczbę nie posiadającą czynników 2 i 3. Na przykład może to być:

c = 7

Wyrażenie a-1 musi być podzielne przez 4 i 3.

a - 1 = 4 × 3 = 12
a = 12 + 1 = 13

Otrzymujemy następujący wzór generatora LCG:

X_n = (13×X_n-1+7)%12 → LCG(12,13,7)

Ponieważ wzór ten pozwala obliczyć kolejną liczbę pseudolosową X_n z liczby poprzedniej X_n-1, musimy określić wartość startową X₀, od której rozpocznie się generacja liczb pseudolosowych. Wartość tę nazywamy ziarnem pseudolosowym (ang. pseudorandom seed). Ziarno wpływa na miejsce w pierścieniu liczb pseudolosowych, od którego rozpocznie się generacja następnych liczb.

Przyjmijmy X₀ = 0 i policzmy wszystkie kolejne liczby pseudolosowe, które tworzy nasz generator LCG:

X₁ = 13 ×	0 + 7 mod 12 =	7 mod 12 =	7
X₂ = 13 ×	7 + 7 mod 12 =	98 mod 12 =	2
X₃ = 13 ×	2 + 7 mod 12 =	33 mod 12 =	9
X₄ = 13 ×	9 + 7 mod 12 =	124 mod 12 =	4
X₅ = 13 ×	4 + 7 mod 12 =	59 mod 12 =	11
X₆ = 13 ×	11 + 7 mod 12 =	150 mod 12 =	6
X₇ = 13 ×	6 + 7 mod 12 =	85 mod 12 =	1
X₈ = 13 ×	1 + 7 mod 12 =	20 mod 12 =	8
X₉ = 13 ×	8 + 7 mod 12 =	111 mod 12 =	3
X₁₀ = 13 ×	3 + 7 mod 12 =	46 mod 12 =	10
X₁₁ = 13 ×	10 + 7 mod 12 =	137 mod 12 =	5
X₁₂ = 13 ×	5 + 7 mod 12 =	72 mod 12 =	0
X₁₃ = 13 ×	0 + 7 mod 12 =	7 mod 12 =	7	= X₁ – ciąg zaczyna się powtarzać
X₁₄ = 13 ×	7 + 7 mod 12 =	98 mod 12 =	2	= X₂

Dla X₀ = 0 otrzymaliśmy ciąg liczb pseudolosowych: 7 2 9 4 11 6 1 8 3 10 5 0 7 2 9 4 ...

Jeśli przyjmiemy inną wartość za X₀, to otrzymamy ten sam ciąg, lecz startujący od innego punktu:

Dla X₀ = 1 mamy : 8 3 10 5 0 7 2 9 4 11 6 1 ...
Dla X₀ = 2 mamy : 9 4 11 6 1 8 3 10 5 0 7 2 ...
Dla X₀ = 3 mamy : 10 5 0 7 2 9 4 11 6 1 8 3 ...

Następstwo kolejnych liczb pseudolosowych jest zawsze takie samo – np. po liczbie 3 zawsze wystąpi liczba 10.

Z powyższych rozważań można wyciągnąć wniosek, iż każdy generator LCG da się jednoznacznie scharakteryzować czwórką parametrów:

LCG(m,a,c,X₀)
m  – moduł
a  – mnożnik
c  – przyrost
X₀ – ziarno

Python

# Generator pseudolosowy
#-----------------------

# współczynniki
m = 12
a = 13
c = 7

# ziarno pseudolosowe
x0 = 0

for i in range(m):
    x0 = (a * x0 + c) % m
    print(x0)

W praktycznych realizacjach dąży się do dużych okresów generatora LCG – wtedy liczby pseudolosowe powtarzają się dopiero po wielu miliardach przebiegów. Jako przykład niech posłuży poniższy generator LCG zaproponowany przez prof. D. Knutha:

LCG(34359738368,3141592653, 2718281829, X_o)

m = 34359738368 = 2³⁵ a = [π × 10⁹]
c = [e × 10⁹], e – podstawa logarytmów naturalnych, e = 2,7182818284590452353602874713527...

Do zapamiętania:

Generatory LCG addytywne i multiplikatywne i czym się różnią.
Cechy generatora LCG.
Metoda wyznaczania współczynników generatora LCG.

do podrozdziału do strony

Język Python posiada wbudowany moduł generacji liczb pseudolosowych o nazwie random. Aby go uaktywnić, na początku programu umieść polecenie:

Python

# Liczby pseudolosowe
#--------------------

import random
...

Moduł random posiada wiele wbudowanych funkcji, które obsługują liczby pseudolosowe. Funkcje te wywołujemy poprzez nazwę random:

random.funkcja(parametry)

random.randrange(zakres)

Funkcja generuje całkowitą liczbę pseudolosową z podanego zakresu. Parametr zakres posiada takie samo znaczenie jak w funkcji range( ) stosowanej w pętlach for.

random.randrange(n)

Generuje całkowitą liczbę pseudolosową z zakresu od 0 do n-1. Poniższy program generuje wyniki rzutów kostką do gry:

Python

# Liczby pseudolosowe
#--------------------

import random

# 9 rzutów kostką
for i in range(9):
    wynik = random.randrange(1,7)
    print("Rzut nr",i+1,":",wynik)

random.randrange(n) – całkowita liczba pseudolosowa od 0 do n-1,
random.randrange(m,n) – całkowita liczba pseudolosowa od m do n-1,
random.randrange(m,n,s) – całkowita liczba pseudolosowa od m do n-1 z krokiem co s.

random.randint(start,stop)

Generuje całkowitą liczbę pseudolosową z zakresu od start do stop włącznie. Program generacji rzutów kostką jest następujący:

Python

# Liczby pseudolosowe
#--------------------

import random

# 9 rzutów kostką
for i in range(9):
    wynik = random.randint(1,6)
    print("Rzut nr",i+1,":",wynik)

random.random( )

Generuje rzeczywistą liczbę pseudolosową x o zakresie 0.0 ≤ x < 1.0 – liczba x może być równa 0, lecz zawsze jest mniejsza od 1. Program generuje 10 rzeczywistych liczb pseudolosowych:

Python

# Liczby pseudolosowe
#--------------------

import random

for i in range(10):
    print(random.random())

Aby otrzymać rzeczywistą liczbę pseudolosową z zakresu a ≤ x < b, użyj wzoru:

x = a + random.random * (b - a)

Python

# Liczby pseudolosowe
#--------------------

import random

x = input("Wpisz dwie liczby: ").split()
a = float(x[0])
b = float(x[1])
for i in range(10):
    print(a + random.random() * (b - a))

do podrozdziału do strony

Tablica pseudolosowa to tablica wypełniona liczbami pseudolosowymi. Tablica taka służy do testowania różnych algorytmów, które wymagają dużej ilości danych losowych. Można ją utworzyć na wiele sposobów. Poniższy program tworzy 100 elementową tablicę i wypełnia ją liczbami pseudolosowymi z zakresu od 10 do 99 (99 włącznie).

Sposób 1:

Python

# Tablica pseudolosowa
#---------------------

import random

# Tworzymy pustą tablicę/listę
t = []
# Dodajemy 100 elementów
for i in range(100):
    t.append(random.randint(10,99))
print(t)

Sposób 2:

Python

# Tablica pseudolosowa
#---------------------

import random

# Tworzymy 100 elementową tablicę/listę
t = [0] * 100
# Zmieniamy elementy
for i in range(100):
    t[i] = random.randint(10,99)
print(t)

Sposób 3:

Python

# Tablica pseudolosowa
#---------------------

import random

# Tworzymy 100 elementową tablicę/listę
t = [random.randint(10,99) for i in range(100)]
print(t)

Sposób 3 wymaga wyjaśnienia. Tutaj pętla for jest wykorzystana bezpośrednio do definiowania kolejnych elementów tablicy listy. Składnia jest następująca:

nazwa = [wyrażenie for i in range(zakres)]

Kolejne obiegi pętli for powodują wyliczenie wartości wyrażenia i przypisanie jej do kolejnych elementów tablicy. Na przykład potrzebujemy tablicy ze 100 kolejnymi liczbami parzystymi:

Python

# Tworzymy 100 elementową tablicę/listę
t = [2 * i for i in range(100)]
print(t)

W przypadku tablicy pseudolosowej każdy obieg pętli for powoduje obliczenie wyrażenia random.randint(10,99). Wynikiem jest liczba pseudolosowa od 10 do 99. Liczba ta zostanie przypisana kolejnemu elementowi tworzonej tablicy listy. Elementów powstanie tyle, ile razy wykona się pętla for. W wyrażeniu można korzystać z wartości zmiennej pętli for (tutaj i).

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Klasa III

Liczby pseudolosowe

SPIS TREŚCI

Co to jest liczba pseudolosowa?

Do zapamiętania:

Generatory liczb pseudolosowych

Do zapamiętania:

Liczby pseudolosowe w Pythonie

random.randrange(zakres)

random.randrange(n)

random.randint(start,stop)

random.random( )

Tablica pseudolosowa

Sposób 1:

Sposób 2:

Sposób 3: