Generator liczb pseudolosowych (ang. PRNG - Pseudo-Random Number Generator) pozwala na generowanie ciągu liczb, który:

• jest deterministyczny - zainicjowany tą samą wartością dają zawsze taki sam ciąg pseudolosowych liczb,
• pod pewnymi względami jest nieodróżnialny od ciągu uzyskanego z prawdziwie losowego źródła.

Generatory liczb pseudolosowych znajdują zastosowania w wielu dziedzinach algorytmiki, są to m.in:

• algorytmy genetyczne - selekcja oraz mutacja
• algorytmy heurystyczne - symulowane wyżarzanie
• sztuczna inteligencja - początkowe wartości połączeń pomiędzy neuronami
• algorytmy probabilistyczne - metody Monte-Carlo

Najbardziej znanym sposobem generowania liczb pseudolosowych jest metoda opracowana przez Lehmer'a w 1951 zwana liniowym generatorem kongruentnym (ang. LCG - Linear Congruential Generator). Polega ona na obliczaniu kolejnych liczb pseudolosowych: x₁, x₂, ... x_n o zakresie wartości 0 .. m-1 na podstawie poniższego wzoru:
gdzie: x₁ jest początkową wartością, którą inicjuje się generator - tzw. ziarnem (ang. seed).

Warto zauważyć, że cechą tego generatora jest fakt, iż jeżeli kolejna wygenerowana liczba powtarza się w ciągu liczb już wygenerowanych to wpadamy w cykl: x₁, x₂, x₃, ..., x₁, x₂, x₃, ....
Jeżeli zainicjujemy kolejne generowanie liczbą x₂, to otrzymamy oczywiście ciąg: x₂, x₃, ..., x₁, x₂, x₃, .... W praktyce, jeżeli chcemy uzyskać nieznany ciąg to inicjujemy taki generator wartością, która nie będzie znana w momencie wykonywania programu - np. wartością zegara systemowego. Czasem jednak właściwość generowania znanego ciągu na podstawie wartości ziarna jest jak najbardziej pożądana - na przykład podczas szyfrowania metodą XOR.

Na temat tego prostego wzoru powstało bardzo dużo opracowań i analiz matematycznych, które mówią nam jakie najlepiej dobrać współczynniki m oraz b w celu uzyskania dobrego generatora liczb pseudolosowych. Dobrego, czyli takiego, w którym cykl będzie jak najdłuższy. Łatwo zauważyć, że maksymalna długość cyklu takiego generatora wynosi m.

• m powinno być duże, często wybiera się tutaj potęgi 10 albo 2,
• a nie powinno być zbyt duże, ale też nie za małe - dobrym wyborem jest tutaj liczba o jeden rząd mniejsza (o jedną cyfrę krótsza) od m,
• dobrą wartością a jest liczba postaci t21, gdzie t jest liczbą parzystą.

D.E.Knuth pokazał, iż niektóre wartości mogą prowadzić do wygenerowania bardzo, krótkich cykli co oczywiście jest wysoce niepożądane. Na przykład dla b=19, m=381 oraz x₁=0 otrzymamy sekwencję: 0, 1, 20, 0, 1, 20, ...

Generator opracowany przez Lehmer'a możemy uogólnić następująco:

Generator mieszany	x_i = (a * x_{i-1} + c) \mod m
Generator multiplikatywny	x_i = (a * x_{i-1}) \mod m

Generatory używane w praktyce posiadają następujące wartości współczynników:

Nazwa	m	a	c
Numerical Recipes	232	1664525	1013904223
Borland C/C++	232	22695477	1
GNU Compiler Collection	232	69069	5
ANSI C	232	1103515245	12345
Borland Delphi, Virtual Pascal	232	134775813	1
Microsoft Visual/Quick C/C++	232	214013	2531011
ANSIC	231	1103515245	12345
MINSTD	231-1	16807	0
RANDU	231	65539	0
SIMSCRIPT	231-1	630360016	0
BCSLIB	235	30517578125	7261067085
BCPL	232	2147001325	715136305
URN12	231	452807053	0
APPLE	235	1220703125	0
Super-Duper	232	69069	0
FISH	231-1	950706376	0
SIMULA	235	30517578125	0
NAG	259	302875106592253	0
DRAND 48	248	25214903917	11
CRAY	248	44485709377909	0
MAPLE	1012-11	427619669081	0
DERIVE	232	3141592653	1
CRAND	232	663608941	0

Algorytm obliczania (a * b) mod m bez przepełnienia

Zwróćmy uwagę, iż bardzo prawdopodobne jest wykroczenie poza zakres reprezentacji liczb w programie w miejscu mnożenia a * x_i-1. Gdy zachodzi taka sytuacja, następuje przerwanie programu z powodu wystąpienia wyjątku przepełnienia. Bądź, jeżeli język, który zastosowaliśmy nie sprawdza takiej sytuacji, dochodzimy do sytuacji, w której cykl naszego generatora ulega skróceniu, co oczywiście jest cechą niepożądaną. Poniżej przedstawiono algorytm, który pozwala obliczać wartość (a * x) mod m dla wartości m < zakres reprezentacji liczb / 2. Czyli jeżeli w naszym programie użyjemy 64-bitową reprezentację liczb, wówczas możemy obliczyć wszystkie takie operacje dla m < 2⁶³, co oczywiście pozwala nam na użycie dowolnego generatora przedstawionego w tabelce powyżej.

Rozłóżmy na początek liczbę a na jej reprezentację binarną: gdzie n oznacza liczbę bitów reprezentującą daną liczbę.
Zatem mnożenie a * x możemy teraz przedstawić jako: Co daje nam: Zauważmy, że współczynniki a_i są równe 0 bądź 1. Zatem przedstawiony powyżej wzór sprowadza się do dodania odpowiednich iloczynów (2ⁱ*x). Każdy taki iloczyn występujący we wzorze jest dwa razy większy od poprzedniego więc cały algorytm mnożenia możemy przedstawić następująco:

b = 1;
n = 1;
result = 0;
while (n <= 64) /* Dla wszystkich bitów w reprezentacji */
{
  if(a & b != 0) /* dla bitów różnych od 0 */
  {
     result = (result + x) % m;
  }
  x = (x + x) % m /* Obliczanie kolejnego współczynnika (2i*x) */
  b = 2 * b;
  n = n + 1;
}
return result;


Generowanie liczb pseudolosowych z zakresu <a, b>

Jeżeli chcemy wygenerować ciąg liczb pseudolosowych z zadanego zakresu, nie powinniśmy modyfikować współczynnika m w przytoczonych przykładach. Parametry przedstawione w nich są tak dobrane by osiągnąć jak najdłuższy cykl generowanych liczb pseudolosowych. Należy zatem losowane liczby sprowadzić do interesującego nas przedziału. Można to zrobić następująco (przez rand() oznaczymy przedstawiony wcześniej generator liczb pseudolosowych): a + (rand() mod (b-a+1)).