Wbudowane generatory liczb pseudolosowych


Tematy pokrewne   Podrozdziały
Przedziały liczbowe i liczby
Liczby parzyste i nieparzyste
Liczby podzielne lub niepodzielne przez zadane podzielniki
Ciągi arytmetyczne
NWD – algorytm Euklidesa
Liczby względnie pierwsze
Najmniejsza wspólna wielokrotność
Odwrotność modulo – rozszerzony algorytm Euklidesa
Liczby pierwsze – generacja przez sprawdzanie podzielności
Liczby pierwsze – generacja sitem Eratostenesa
Liczby pierwsze – generacja sitem liniowym
Liczby pierwsze – generacja sitem Atkina-Bernsteina
Czynniki pierwsze – metoda próbnych dzieleń
Czynniki pierwsze – metoda Fermata
Pierwszość liczby naturalnej – algorytmy naiwne
Pierwszość liczby naturalnej – Chiński Test Pierwszości
Pierwszość liczby naturalnej – Małe Twierdzenie Fermata
Pierwszość liczby naturalnej – test Millera-Rabina
Liniowe generatory liczb pseudolosowych
Generator pseudolosowy Park-Miller
Generator pseudolosowy Mersenne Twister
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Liczby Fibonacciego
System liczbowy Fibonacciego
Całkowity pierwiastek kwadratowy
  Lazarus
Code::Blocks
Free Basic

 

Współczesne języki programowania posiadają wbudowane generatory liczb pseudolosowych udostępniające programiście swoje funkcje poprzez prosty interfejs. W tym rozdziale pokażemy, jak się z tych funkcji korzysta we własnych programach.

 

Lazarus

Inicjalizacja

Ziarno generatora pseudolosowego (ang. random seed) można zainicjować w języku Lazarus na dwa sposoby. W pierwszym odwołujemy się bezpośrednio do zmiennej przechowującej ziarno:

 

randseed := nowa wartość dla ziarna pseudolosowego;

 

Po takiej inicjalizacji generator pseudolosowy będzie produkował zawsze ten sam ciąg liczb pseudolosowych, co można wykorzystać do prostej, amatorskiej kryptografii (zwykłe generatory LCG nie są zalecane dla profesjonalnych systemów kryptograficznych).

Drugi sposób wykorzystuje procedurę:

 

randomize;

 

Procedura randomize inicjuje randseed wartością odczytaną z zegara systemowego. Ponieważ zegar systemowy w komputerach IBM-PC działa niezależnie od reszty sprzętu, możemy go potraktować jako źródło wartości losowych – nie wiadomo przecież, w którym momencie zostanie wywołana procedura randomize. Procedurę tę wywołujemy zwykle tylko jeden raz na samym początku programu.

Zupełnie bez sensu jest poniższa konstrukcja programowa:

 

...
for i := 1 to 10 do
begin
  randomize;
  writeln(random(100));
end;
...
 

Jeśli komputer działa szybko, to zegar systemowy, z którego procedura randomize pobiera czas, nie zdąży się zmienić w pętli. Zatem w każdym obiegu pętli ziarno generatora pseudolosowego będzie inicjowane tą samą wartością. W efekcie generator wyprodukuje tę samą liczbę pseudolosową – aczkolwiek zwykle różną w kolejnych uruchomieniach programu, gdyż czas zegara będzie wtedy inny. Poniżej mamy wynik działania programu.

 

Zawartość okna konsoli
81
81
81
81
81
81
81
81
81
81

 

Poprawnie program powinien wyglądać tak:

 

...
randomize;          // inicjujemy generator pseudolosowy
...
for i := 1 to 10 do // generujemy liczby pseudolosowe
begin
  writeln(random(100));
end;
...
 

Generacja całkowitych liczb pseudolosowych

Do generacji całkowitych liczb pseudolosowych wykorzystujemy funkcję random(n), która zwraca wartość pseudolosową w zakresie od 0 do n-1. Parametr n może być liczbą 32 bitową longint lub 64 bitową int64. Wtedy wynik funkcji również jest tego samego typu. Jeśli chcemy wygenerować liczbę pseudolosową z przedziału domkniętego <a,b>, to stosujemy następujące wyrażenie:

 

a + random(a - b + 1)

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Przykładowy program generuje 10 liczb pseudolosowych z przedziału <10,20>:

 

Lazarus
// Wewnętrzny generator pseudolosowy
// Data:   17.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------------

program prg;

var i : integer;

begin
  randomize;
  for i := 1 to 10 do writeln(10 + random(11));
end.

 

Zawartość okna konsoli
19
20
16
19
19
16
11
15
12
18

 

Generacja rzeczywistych liczb pseudolosowych

Liczby rzeczywiste generuje funkcja random bez parametrów. Zwraca wtedy wartość zmiennoprzecinkową typu extended (20 cyfr znaczących) z przedziału <0,1) – od 0 domknięty do 1 otwarty.

Jeśli chcemy wygenerować pseudolosową liczbę rzeczywistą z przedziału <a,b) (a domknięty, b otwarty), stosujemy wzór:

 

a + random * (b - a)

 

Jeśli chcemy wygenerować pseudolosową liczbę rzeczywistą z przedziału (a,b> (a otwarty, b domknięty), stosujemy wzór:

 

a + (1 - random) * (b - a)

 

Jeśli chcemy wygenerować pseudolosową liczbę rzeczywistą z przedziału <a,b> (obustronnie domknięty), stosujemy wzór:

 

a + random(2147483647) / 2147483646 * (b - a)

 

Jeśli chcemy wygenerować pseudolosową liczbę rzeczywistą z przedziału (a,b) (obustronnie otwarty), stosujemy wzór:

 

a + (1 + random(2147483646)) / 2147483647 * (b - a)

 

Code::Blocks

Inicjalizacja

Generator pseudolosowy jest inicjowany za pomocą funkcji:

 

srand(x0);

 

Funkcja srand() wymaga dołączenia pliku nagłówkowego cstdlib. Argument x0 zostanie użyty jako ziarno generacji liczb pseudolosowych.  Oby otrzymywać w programach bardziej losowe ciągi liczb pseudolosowych, generator inicjujemy wybraną wartością losową, np. wynikiem funkcji time(), który zmienia się co sekundę. Funkcja time() wymaga dołączenia pliku nagłówkowego time.h. Na początku programu umieszczamy następujące wywołanie:

 

...
srand((unsigned)time(NULL));
...
 

Ponieważ czas jest zliczany niezależnie od procesów obliczeniowych komputera, nie wiadomo, w którym momencie program zostanie uruchomiony i wywołana będzie funkcja time(). Dlatego jej wynik możemy potraktować jako losowy. Wpisanie go do ziarna generatora pseudolosowego spowoduje generowanie innej sekwencji liczb pseudolosowych przy każdym uruchomieniu programu.

Inicjalizację generatora pseudolosowego wykonujemy tylko jeden raz, zawsze na początku programu, przed generacją liczb pseudolosowych. Nie ma sensu umieszczanie wywołania funkcji srand(time(NULL)) wewnątrz pętli tworzącej kolejne liczby pseudolosowe – efekt będzie wręcz odwrotny do zamierzonego. Zobacz na podobny przykład w Pascalu!

 

Generacja całkowitych liczb pseudolosowych

Dostęp do kolejnych liczb pseudolosowych uzyskujemy za pomocą funkcji rand(), która zwraca wygenerowaną przez generator liczbę pseudolosową z zakresu od 0 do RAND_MAX (stała RAND_MAX zdefiniowana jest w pliku nagłówkowym cstdlib i ma wartość 32767 = 215 - 1). Funkcja rand() nie zwraca całej liczby pseudolosowej, tylko jej górne 15 bitów. Takie rozwiązanie przyjęto dlatego, iż okazuje się, że generatory LCG generują młodsze bity z mniejszymi okresami powtarzania niż okresy bitów starszych. Zwracanie starszych bitów po części niweluje tę wadę.

Jeśli wystarcza nam 15 bitowy zakres liczb pseudolosowych, to do generacji liczby pseudolosowej w przedziale <a,b> stosujemy prosty wzór:

 

a + rand() % (b - a + 1)

 

Lepszym rozwiązaniem będzie sprowadzenie wyniku rand() do wartości zmiennoprzecinkowej w przedziale <0,1>, a następnie wykorzystanie tej wartości do generacji liczby pseudolosowej w przedziale całkowitym <a,b>.

 

a + (int)(((double)rand() / (double)RAND_MAX) * (b - a))

 

Jeśli potrzebujemy większego zakresu liczb pseudolosowych niż 15 bitów, to możemy wykorzystać funkcję rand() kilkakrotnie:

 

16 bitów: 
(rand() | (rand() << 15)) & 0xFFFF
20 bitów: 
(rand() | (rand() << 15)) & 0xFFFFF
24 bity: 
(rand() | (rand() << 15)) & 0xFFFFFF
32 bity: 
(rand() | (rand() << 15) | (rand() << 30)) & 0xFFFFFF

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

 

Program demonstruje sposób uzyskania 64-bitowych liczb pseudolosowych przy pomocy wbudowanego generatora pseudolosowego. Lepszym jednakże rozwiązaniem jest zaprojektowanie własnego generatora pseudolosowego o okresie 64-bitowym, ponieważ jakość tak otrzymanych liczb pseudolosowych nie jest najlepsza.

 

Code::Blocks
// Generacja 64-bitwych liczb pseudolosowych
// Data:   18.04.2008
// (C)2012 mgr Jerzy Wałaszek
//------------------------------------------

#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

typedef unsigned long long ulong;

int main()
{
  ulong X;
  int i;
  
  srand((unsigned)time(NULL));
  
  for(i = 1; i <= 20; i++)
  {
    X = (ulong)rand()|((ulong)rand()<<15)|((ulong)rand()<<30)|((ulong)rand()<<45)|((ulong)rand()<<60);
    cout << setw(20) << X << endl;
  }
  cout << endl;
  return 0;
}

 

Zawartość okna konsoli
14287740268258102790
18201948344639034413
 5668028842739046048
  542349849068285525
 4472085174507448855
 5136086965452494067
   16439939500462121
15973381195178743161
11574466793181441461
14401113533160066682
16435464985454005274
 5907038298318477603
 3722099091437753545
14124984979157357723
16228289200691414138
11044688875893913486
 1226176721192551851
 3351322725318429551
14137993131048917066
 3949030839947032118

 

Generacja rzeczywistych liczb pseudolosowych

Do generacji rzeczywistych liczb pseudolosowych wynik funkcji rand() sprowadzamy do przedziału {0...1}, a następnie otrzymaną wartość wykorzystujemy do uzyskania rzeczywistej liczby pseudolosowej. Poniżej podajemy prosty sposób realizacji tego zadania.

 

<0,1)  
: (double)rand() / (double)(RAND_MAX + 1)
<0,1> 
: (double)rand() / (double)(RAND_MAX)
 (0,1> 
: 1 - (double)rand() / (double)(RAND_MAX + 1)
(0,1) 
: (double)(1 + rand()) / (double)(RAND_MAX + 2)

 

Rzeczywistą liczbę pseudolosową z przedziału {0...1} wykorzystujemy do generacji liczby pseudolosowej w przedziale {a...b} następująco:

 

a + liczba_pseudolosowa{0...1} * (b - a)

 

Na przykład chcemy wygenerować liczbę pseudolosową w przedziale od a = 2.5 do b = 4.0 włącznie. Przedział ma być domknięty, zatem potrzebujemy liczby pseudolosowej z przedziału domkniętego <0,1>. Wzór jest następujący:

 

2.5 + (double)rand() / (double)(RAND_MAX) * 1.5

 

Free Basic

Inicjalizacja

Ziarno generatora pseudolosowego inicjujemy za pomocą instrukcji:

 

Randomize X0

 

Aby otrzymywać przy każdym uruchomieniu programu inne sekwencje liczb pseudolosowych, jako ziarno stosuje się wartość licznika czasu:

 

Randomize Timer

 

Inicjalizację generatora pseudolosowego wykonuje się jeden raz na samym początku programu. Zobacz na odpowiednie przykłady dla języka Pascal – w Basicu jest bardzo podobnie.

 

Generacja całkowitych liczb pseudolosowych

W języku Basic istnieje funkcja Rnd, która zwraca tylko rzeczywistą wartość pseudolosową z przedziału <0,1) (lewostronnie domkniętego, prawostronnie otwartego). Aby otrzymać liczbę pseudolosową z przedziału całkowitego <a,b>, stosujemy następujące wyrażenie:

 

a + Int(Rnd * (b - a + 1))    lub   a + Cint(Rnd * (b - a))

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

 

Program wyświetla 15 liczb pseudolosowych z przedziału całkowitego <20,30>.

 

Free Basic
' Wbudowany generator liczb pseudolosowych
' Data:   18.04.2008
' (C)2012 mgr Jerzy Wałaszek
'-----------------------------------------

Dim i As Integer

Randomize Timer

For i = 1 To 15
  Print Int(Rnd * 11) + 20
Next
End

 

Zawartość okna konsoli
 26
 23
 30
 28
 26
 27
 20
 27
 25
 30
 25
 27
 26
 22
 25

 

Generacja rzeczywistych liczb pseudolosowych

W języku Basic funkcja Rnd zwraca rzeczywistą liczbę pseudolosową z przedziału <0,1).

Aby uzyskać rzeczywistą liczbę pseudolosową w przedziale <a,b) stosujemy wyrażenie:

 

a + Rnd * (b - a)

 

Aby uzyskać rzeczywistą liczbę pseudolosową w przedziale (a,b> stosujemy wyrażenie:

 

a + (1 - Rnd) * (b - a)

 

Aby uzyskać rzeczywistą liczbę pseudolosową w przedziale domkniętym <a,b> stosujemy konstrukcję:

 

If Rnd > 0.5) Then
    x = a + Rnd * (b - a)
Else
    x = a + (1 - Rnd) * (b - a)
End If
 

Aby uzyskać rzeczywistą liczbę pseudolosową w przedziale otwartym (a,b) stosujemy konstrukcję:

 

Do
    x = a + Rnd * (b - a)
Loop Until x <> a
 


List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.