Liniowe 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
  Liczby pseudolosowe
Generatory LCG
Własności generatorów LCG
Liczby pseudolosowe w przedziale

 

Liczby pseudolosowe

Liczba losowa (ang. random number) jest liczbą r należącą do pewnego zbioru wartości {r1, ..., rn} wybieranych z pewnym prawdopodobieństwem. Jeśli jako r może pojawić się każda z liczb zbioru z tym samym prawdopodobieństwem p(r) = 1/n, to mówimy o równomiernym rozkładzie prawdopodobieństwa liczb losowych z tego zbioru. Na przykład rozważmy rzut kostką. Każdy rzut daje liczbę losową r ze zbioru {1,2,3,4,5,6}. Jeśli kostka nie jest oszukana, to każda z możliwych wartości r pojawia się w rzucie kostką z prawdopodobieństwem p(r) = 1/6. Liczby losowe r posiadają zatem równomierny rozkład prawdopodobieństwa.

Problem z otrzymaniem liczb losowych wynika z deterministycznego charakteru komputera i wykonywanych przez niego operacji. Gdy człowiek dokonuje rzutu kością, nie wie co wypadnie. Taka sama operacja na komputerze wymaga 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ą prawie wcale.

Z drugiej strony liczby losowe używane są powszechnie przy programowaniu komputerów – 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ą liczby losowe, w przeciwnym razie totolotek straciłby sens.

 

Generatory LCG

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:

 

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

 

Ze wzoru wynika, iż kolejna liczba pseudolosowa Xn powstaje z poprzedniej Xn-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 Xn jest resztą z dzielenia przez moduł m. Skoro tak, to może 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ć:

 

X0X1X2 → ...  → Xm-2  → Xm-1X0X1 → ...

 

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

 

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

 

Addytywny LCG: Xn = (aXn-1 + c) mod m
Multiplikatywny LCG: Xn = aXn-1 mod 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 multiplikatywne 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...Xmax (dla LCG multiplikatywnego jest to 1...Xmax). Moduł m jest zawsze o 1 większy od maksymalnej liczby w zakresie, czyli:

 

m = Xmax + 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:

 

Xmax = 11
m = Xmax + 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:    Xn = (13 × Xn-1 + 7) mod 12   → LCG(12,13,7)

 

Ponieważ wzór ten pozwala obliczyć kolejną liczbę pseudolosową Xn z liczby poprzedniej Xn-1, musimy określić wartość startową X0, 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 X0 = 0 i policzmy wszystkie kolejne liczby pseudolosowe, które tworzy nasz generator LCG:

 

X1 = 13 ×   0 + 7 mod 12 =  7 mod 12 =  7  
X2 = 13 ×  7 + 7 mod 12 =  98 mod 12 =  2  
X3 = 13 ×  2 + 7 mod 12 =  33 mod 12 =  9  
X4 = 13 ×  9 + 7 mod 12 =  124 mod 12 =  4  
X5 = 13 ×  4 + 7 mod 12 =  59 mod 12 =  11  
X6 = 13 ×  11 + 7 mod 12 =  150 mod 12 =  6  
X7 = 13 ×  6 + 7 mod 12 =  85 mod 12 =  1  
X8 = 13 ×  1 + 7 mod 12 =  20 mod 12 =  8  
X9 = 13 ×  8 + 7 mod 12 =  111 mod 12 =  3  
X10 = 13 ×  3 + 7 mod 12 =  46 mod 12 =  10  
X11 = 13 ×  10 + 7 mod 12 =  137 mod 12 =  5  
X12 = 13 ×  5 + 7 mod 12 =  72 mod 12 =  0  
X13 = 13 ×  0 + 7 mod 12 =  7 mod 12 =  7  = X1 – ciąg zaczyna się powtarzać
X14 = 13 ×  7 + 7 mod 12 =   98 mod 12 =  2  = X2
...

 

Dla X0 = 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 X0, to otrzymamy ten sam ciąg, lecz startujący od innego punktu:

 

Dla X0 = 1 mamy : 8 3 10 5 0 7 2 9 4 11 6 1 ...
Dla X0 = 2 mamy : 9 4 11 6 1 8 3 10 5 0 7 2 ...
Dla X0 = 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,X0)
m – moduł
a – mnożnik
c – przyrost
X0 – ziarno

 

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, Xo)

m = 34359738368 = 235
a = [π × 109]
c = [e × 109],  e – podstawa logarytmów naturalnych, e = 2,7182818284590452353602874713527...

 

 

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.

 

Poniższy program zawiera generator LCG. W pierwszym wierszu na wejściu należy umieścić cztery liczby m, a, c oraz X0. W następnych wierszach program wyświetla kolejne liczby pseudolosowe generowane przez zadany współczynnikami generator LCG aż do zamknięcia cyklu. Ambitnym czytelnikom proponujemy drobną rozbudowę tego programu o licznik wygenerowanych liczb pseudolosowych. Po zakończeniu działania głównej zawartość licznika powinna zostać wypisana, aby użytkownik mógł sprawdzić, czy generator LCG miał cykl maksymalny równy m – przy źle dobranych współczynnikach m, a i c cykl generatora może się zamykać szybciej niż po wygenerowaniu m liczb pseudolosowych.

 

Lazarus Code::Blocks Free Basic
// Generator LCG
// Data   : 8.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

var m,a,c,x,x0 : qword;

begin
  readln(m,a,c,x0);
  x := x0;
  repeat
    x := (a * x + c) mod m;
    write(x,' ');
  until x = x0;
  writeln;
end.
// Generator LCG
// Data   : 8.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

int main()
{    
  unsigned long long m,a,c,x,x0;

  cin >> m >> a >> c >> x0;
  x = x0;
  do
  {
    x = (a * x + c) % m;
    cout << x << " ";
  } while(x != x0);
  cout << endl;
  return 0;
}
' Generator LCG
' Data   : 8.04.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

Dim As Ulongint m,a,c,x,x0

Input m,a,c,x0
x = x0
Do
  x = (a * x + c) Mod m
  Print x;" ";
Loop Until x = x0
Print
End
Wynik
  12 13 7 0
7 2 9 4 11 6 1 8 3 10 5 0
 
 

Generator LCG
(C)2012 mgr Jerzy Wałaszek

m = , a = , c = , X0 =


...

 

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.

 

Poniżej mamy prosty program wyliczający współczynniki addytywnego generatora LCG na podstawie maksymalnej liczby pseudolosowe Xmax, którą należy podać na wejściu w pierwszym wierszu. W następnych wierszach program wypisuje wyliczone współczynniki m, a i c. Program korzysta z wbudowanego generatora liczb pseudolosowych.

 

Lazarus
// Współczynniki generatora LCG
// Data   : 10.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

function NWD(a,b : qword) : qword;
var t : qword;
begin
  while b <> 0 do
  begin
    t := b; b := a mod b; a := t;
  end;
  NWD := a;
end;

var m,a,c,x,d,g : qword;

begin
  randomize;
  readln(x);
  m := x + 1;
  repeat
    c  := random(m);
  until NWD(m,c) = 1;
  a := 1; x := m; d := 2; g := round(sqrt(m));
  while d <= g do
  begin
    if x mod d = 0 then
    begin
      a := a * d;
      repeat
        x := x div d;
      until x mod d <> 0;
    end;
    if d = 2 then inc(d) else inc(d,2);
    if x < d then break;
  end;
  a := a * x;
  if m mod 4 = 0 then a := a * 2;
  inc(a);
  writeln('m = ',m:12);
  writeln('a = ',a:12);
  writeln('c = ',c:12);
  writeln;
end.
Code::Blocks
// Współczynniki generatora LCG
// Data   : 10.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

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

using namespace std;

typedef unsigned long long ulong;

ulong NWD(ulong a, ulong b)
{
  ulong t;

  while(b)
  {
    t = b; b = a % b; a = t;
  }
  return a;
}

int main()
{
  ulong m,a,c,x,d,g;

  srand((unsigned)time(NULL));
  cin >> x;
  m = x + 1;
  do c = rand() % m; while(NWD(m,c) != 1);
  a = 1; x = m; d = 2; g = (ulong)sqrt(m);
  while(d <= g)
  {
    if(x % d == 0)
    {
      a *= d;
      do x /= d; while(x % d == 0);
    }
    if(d == 2) d++; else d += 2;
    if(x < d) break;
  }
  a *= x;
  if(m % 4 == 0) a <<= 1;
  a++;
  cout << "m = " << setw(12) << m << endl
       << "a = " << setw(12) << a << endl
       << "c = " << setw(12) << c << endl
       << endl;
  return 0;
}
Free Basic
' Współczynniki generatora LCG
' Data   : 10.04.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

Function NWD(Byval a As Ulongint, Byval b As Ulongint) As Ulongint

  Dim t As Ulongint

  While b
    t = b: b = a Mod b: a = t
  Wend
  NWD = a
End Function

Dim As Ulongint m,a,c,x,d,g

Randomize Timer
Input x
m = x + 1
Do
  c = Culngint(Rnd(1) * m)
Loop Until NWD(m,c) = 1
a = 1: x = m: d = 2: g = Culngint(Sqr(m))
While d <= g
  If x Mod d = 0 Then
    a = a * d
    Do
      x \= d
    Loop Until x Mod d <> 0
  End If
  If d = 2 Then d += 1: Else d += 2
  If x < d Then Exit While
Wend
a *= x
If m Mod 4 = 0 Then a *= 2
a += 1
Print Using "m = ############";m
Print Using "a = ############";a
Print Using "c = ############";c
Print
End
Wynik
9987
m =         9988
a =         9989
c =         1785
 

Współczynniki dla generator LCG
(C)2012 mgr Jerzy Wałaszek

Xmax =


...

 

Poniższy program sprawdza z kolei, czy generator LCG o zadanych współczynnikach m, a i c generuje m liczb w przedziale od 0 do m - 1. Na wejściu program pyta o kolejne współczynniki, po czym sprawdza generator i wypisuje ilość wygenerowanych wartości oraz wyraz OK, jeśli ta ilość jest równa m. Program kończy się po podaniu za m wartości 0. W programie wykorzystujemy tablicę dynamiczną.

 

Lazarus
// Test generatora LCG
// Data   : 13.04.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program LCGTest;

var
  m,a,c,x,i,count : cardinal;
  T : array of boolean;

begin
  while true do
  begin
     write('m = '); readln(m);    // Czytamy moduł

     if m = 0 then break;         // Jeśli zero, to kończymy

     write('a = '); readln(a);    // Czytamy mnożnik
     write('c = '); readln(c);    // Czytamy przyrost

     SetLength(T,m);              // Tworzymy tablicę dynamiczną

     for i := 0 to m - 1 do       // Wypełniamy ją zerami
        T[i] := false;

     x := 0;                      // Określamy ziarno generatora

     for i := 0 to m - 1 do       // Generujemy m liczb pseudolosowych
     begin
       x := (a * x + c) Mod m;    // Wyznaczamy kolejną liczbę pseudolosową
       T[x] := true;              // i umieszczamy ją na swoim miejscu w tablicy
     end;

     count := 0;

     for i := 0 to m - 1 do
       if T[i] then inc(count);   // Zliczamy wygenerowane liczby

     writeln(count);              // Wyświetlamy ilość wygenerowanych liczb

     if count = m then writeln('OK') // Oceniamy generator
     else              writeln('---');
     writeln;

     SetLength(T,0);              // Usuwamy tablicę dynamiczną
  end;
end.
Code::Blocks
// Test generatora LCG
// Data   : 13.04.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

int main()
{
  unsigned int m,a,c,x,i,count;
  bool * T;

  while(true)
  {
     cout << "m = "; cin >> m;    // Czytamy moduł

     if(!m) break;                // Jeśli zero, to kończymy

     cout << "a = "; cin >> a;    // Czytamy mnożnik
     cout << "c = "; cin >> c;    // Czytamy przyrost

     T = new bool [m];            // Tworzymy tablicę dynamiczną

     for(i = 0; i < m; i++)       // Wypełniamy ją zerami
        T[i] = false;

     x = 0;                       // Określamy ziarno generatora

     for(i = 0; i < m; i++)       // Generujemy m liczb pseudolosowych
     {
        x = (a * x + c) % m;      // Wyznaczamy kolejną liczbę pseudolosową
        T[x] = true;              // i umieszczamy ją na swoim miejscu w tablicy
     }

     count = 0;

     for(i = 0; i < m; i++)
        if(T[i]) count++;         // Zliczamy wygenerowane liczby

     cout << count << endl;       // Wyświetlamy ilość wygenerowanych liczb

     if(count == m) cout << "OK\n\n"; // Oceniamy generator
     else           cout << "---\n\n";

     delete [] T;                 // Usuwamy tablicę dynamiczną
  }

  return 0;
}
Free Basic
' Test generatora LCG
' Data   : 13.04.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

Dim As UInteger m,a,c,x,i,count
Dim As Byte Ptr T

While 1
  Input "m = "; m                 ' Czytamy moduł
  
  If m = 0 Then Exit While        ' Jeśli zero, to kończymy

  Input "a = "; a                 ' Czytamy mnożnik
  Input "c = "; c                 ' Czytamy przyrost

  T = New Byte [m]                ' Tworzymy tablicę dynamiczną

  For i = 0 To m - 1              ' Wypełniamy ją zerami
    T[i] = 0
  Next

  x = 0                           ' Określamy ziarno generatora

  For i = 0 To m - 1              ' Generujemy m liczb pseudolosowych
    x = (a * x + c) Mod m         ' Wyznaczamy kolejną liczbę pseudolosową
    T[x] = 1                      ' i umieszczamy ją na swoim miejscu w tablicy
  Next

  count = 0

  For i = 0 To m - 1
    If T[i] = 1 Then count += 1   ' Zliczamy wygenerowane liczby
  Next
  
  Print Using "&";count           ' Wyświetlamy ilość wygenerowanych liczb

  If count = m Then               ' Oceniamy generator
  	 Print "OK" 
  Else
    Print"---"
  End If
  
  Print
  
  Delete [] T                     ' Usuwamy tablicę dynamiczną

Wend

End
Wynik
m = 71
a = 72
c = 8
71
OK

m = 111
a = 112
c = 9
37
---

 

Własności generatorów LCG

Generatory LCG zostały opracowane dosyć dawno i dzisiaj są już nieco przestarzałe. Posiadają szereg istotnych wad, dlatego nie powinno się ich stosować w aplikacjach, gdzie wymagana jest wysoka przypadkowość danych – np. losowania w grach liczbowych, symulacje ekonomiczne i finansowe, profesjonalne systemy kryptograficzne itp. Natomiast dla potrzeb amatorskich są zupełnie wystarczające ze względu na swoją prostotę – dlatego opisujemy je w naszym serwisie.

Jednym z poważnych problemów generatorów LCG jest to, iż młodsze bity generowanych liczb pseudolosowych posiadają krótszy okres powtarzania niż cała liczba pseudolosowa, jeśli moduł jest potęgą liczby 2 - a tak zwykle jest we wbudowanych generatorach LCG z uwagi na prostotę wyliczania reszty z dzielenia przez moduł, gdzie dzielenie zastępuje się obcinaniem bitów wykraczających poza wartość modułu:

Jeśli m = 2k, to

 

Xn = (a × Xn-1 + c) mod 2k = (a × Xn-1 + c) obcięte do k bitów.

 

Najczęściej k = 16 lub 32, co daje wynik bezpośrednio mieszczący się w komórkach pamięci. Procesor wylicza wyrażenie (a × Xn-1 + c) i wynik umieszcza w 32-bitowym obszarze pamięci, co powoduje automatyczne obcięcie bitów wykraczających poza 31-szą pozycję.

Poniżej podajemy przykładowe parametry generatorów LCG stosowanych w różnych językach programowania (źródło pochodzi z Wikipedii):

 

Źródło m a c Wyjściowe bity ziarna w rand()
lub w Random(L)
Numerical Recipes 232 1664525 1013904223  
Borland C/C++ 232 22695477 1 bity 30..16 w rand(), 30..0 w lrand()
GNU Compiler Collection 232 69069 5 bity 30..16
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++ 232 1103515245 12345 bity 30..16
Borland Delphi, Virtual Pascal 232 134775813 1 bity 63..32 w (seed * L)
Microsoft Visual/Quick C/C++ 232 214013 2531011 bity 30..16
ANSIC 231 1103515245 12345  
MINSTD 231-1 16807 0  
RANDU 231 65539 0  
SIMSCRIPT 231-1 630360016 0  
BCSLIB 235 515 7261067085  
BCPL 232 2147001325 715136305  
URN12 231 452807053 0  
APPLE 235 1220703125 0  
Super-Duper 232 69069 0  

 

Liczby pseudolosowe w przedziale

Problem

Mając dany generator LCG należy wygenerować serie liczb pseudolosowych w przedziale całkowitym <x,y>.

 

 

Jest to typowe zadanie losowania wartości pseudolosowej. Załóżmy, iż tworzymy program gry w kości. W grze będziemy losować wyniki rzutów kostką będące liczbami pseudolosowymi z przedziału całkowitego <1,6>. Na pierwszy rzut oka wygląda na to, iż problem rozwiążemy tworząc generator LCG generujący liczby od 1 do 6 (może to być generator multiplikatywny). Odradzam to rozwiązanie – okres powtarzania takiego generatora jest bardzo krótki i ze względu na własności generatorów LCG po każdych 6 rzutach kostką otrzymywalibyśmy wciąż te same wyniki – przyznasz, że gra straciłaby wiele na atrakcyjności.

Problem rozwiązujemy inaczej – tworzony jest generator LCG o bardzo dużym okresie m - np. m = 264. Następnie wygenerowaną liczbę pseudolosową dzielimy przez 6 i bierzemy resztę z tego dzielenia. Otrzymamy liczby od 0 do 5. Sekwencje tych liczb będą się powtarzały z okresem 264! (przynajmniej teoretycznie jeśli 6 nie dzieli modułu generatora!) Aby sprowadzić wynik do przedziału <1,6> musimy do otrzymanej reszty dodać 1.

Zapiszmy to tak:

 

X ← (a × X + c) mod m
W ← (X mod 6)  + 1

X  – liczba pseudolosowa
m,a,c  – współczynniki generatora LCG
W  – wynik losowania rzutu kostką

 

Powyższy wzór możemy w prosty sposób uogólnić na dowolny przedział całkowity <x,y>. W tym celu obliczamy długość przedziału plus jeden:

 

Lxyy - x + 1

 

Liczba Lxy stanie się dzielnikiem wygenerowanej przez generator liczby pseudolosowej X. Otrzymaną z dzielenia resztę należy zwiększyć o wartość x, aby wpadała w przedział <x,y>:

 

Wxy ← (X mod Lxy) + x

 

Otrzymane w powyższy sposób liczby pseudolosowe mogą cierpieć na zmniejszoną pseudolosowość młodszych bitów w liczbach generowanych przez generator LCG. Istnieje proste i w miarę skuteczne rozwiązanie tego problemu. Liczbę X dzielimy przez m zmiennoprzecinkowo i zapamiętujemy wynik, który jest rzeczywistą liczbą pseudolosową z przedziału <0,1):

 

XRX : m

 

Następnie liczbę XR wymnażamy przez Lxy i jako wynik bierzemy część całkowitą tego iloczynu powiększoną o x:

 

Wxy ← [XR × Lxy] + x

 

Ponieważ teraz przy tworzeniu Wxy są brane pod uwagę wszystkie bity X (a nie tylko te młodsze z reszty z dzielenia, które mają niską przypadkowość), wynik jest "bardziej" pseudolosowy niż w pierwszym rozwiązaniu.

Pozostaje jeszcze jeden, bardzo istotny problem. Generator LCG startując od zadanego ziarna X0 zawsze tworzy ten sam ciąg liczb pseudolosowych. Wynika z tego, iż nasz program powinien przy każdym uruchomieniu wybierać inne ziarno, w przeciwnym razie wylosowane liczby będą się powtarzały – np. zawsze gracze będą wyrzucali te same sekwencje oczek lub będą otrzymywali te same kolejne układy kart w grach losowych przy każdym uruchomieniu programu – w końcu nauczą się ich na pamięć!. W komputerach IBM-PC mamy do dyspozycji tzw. zegar czasu rzeczywistego (ang. RTC – Real Time Clock), który zlicza czas – dzięki niemu komputer IBM-PC utrzymuje poprawną datę i czas systemowy. Czas zliczany jest z dokładnością do milisekund. Przy każdym uruchomieniu programu odczytujemy stan zegara i wykorzystujemy go jako wartość dla ziarna pseudolosowego generatora LCG. W ten sposób ziarno jest każdorazowo inne (nie wiadomo przecież z góry, w jakim czasie użytkownik będzie uruchamiał swój program), zatem sekwencja liczb pseudolosowych wystartuje od innego punktu. W efekcie otrzymamy nieprzewidywalne z góry ciągi pseudolosowe – i o to właśnie chodzi.

 

Algorytm generacji liczb pseudolosowych

Wejście
x, y    początek i koniec przedziału generacji liczb pseudolosowych, x,y C
LCG(m,a,c)  – generator LCG
Wyjście:

Wxy liczba pseudolosowa z przedziału <x,y>.

Elementy pomocnicze:
Lxy    długość przedziału <x,y> + 1
X  – ziarno pseudolosowe oraz liczba pseudolosowa
XR  – rzeczywista liczba pseudolosowa z przedziału <0,1)
Lista kroków:
K01: X ← czas z zegara RTC ; tworzymy przypadkowe ziarno generatora LCG
K02: Powtarzaj wymaganą liczbę razy kroki K03...K07 ; w pętli generujemy pożądaną ilość liczb pseudolosowych
K03:     X ← (a × X + c) mod m ; generujemy liczbę pseudolosową
K04:     XR  ← X : m ; tworzymy rzeczywistą liczbę pseudolosową
K05:     Lxyy - x + 1 ; obliczamy długość przedziału <x,y> plus 1
K06:     Wxy ← ⌊XR × Lxy⌋ + x ; obliczamy liczbę pseudolosową w <x,y>
K07:     Przetwarzaj Wxy ; wykorzystujemy wygenerowaną liczbę pseudolosową
K08: Zakończ  

 

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 odczytuje z pierwszego wiersza trzy liczby x,y oraz n. Liczby x i y określają przedział całkowity, w którym mają być wygenerowane liczby pseudolosowe. Liczba n określa ile liczb pseudolosowych należy wygenerować. Jako generator LCG stosujemy generator zaproponowany przez prof. Donalda Knutha o następujących parametrach:

 

LCG(34359738368, 3141592653, 2718281829, Xo)

 

Do wykonywania mnożenia i dodawania stosujemy procedury mnożenia i dodawania modulo, które opisaliśmy w rozdziale o chińskim teście pierwszości. Dzięki nim rachunki nie przekroczą zakresu liczb 64-bitowych.

 

Lazarus
// Liczby pseudolosowe w <x,y>
// Data   : 12.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

uses SysUtils,DateUtils;

// Zmienne globalne dla LCG
//-------------------------

const a = 3141592653;
      c = 2718281829;
      m = 34359738368;

var X0 : qword;

// Procedura inicjuje ziarno X
//----------------------------
procedure Uprzypadkowij;
var
  t : TDateTime;
begin
  t := Now;
  X0 := HourOf(t);
  X0 := X0 * 60 + MinuteOf(t);
  X0 := X0 * 60 + SecondOf(t);
  X0 := X0 * 1000 + MillisecondOf(t);
end;

// Funkcja oblicza a * b mod n
//----------------------------
function Mnoz(a,b,n : qword) : qword;
var
  m,w : qword;
begin
  w := 0; m := 1;
  while m <> 0 do
  begin
    if b and m <> 0 then w := (w + a) mod n;
    a := (a shl 1) mod n;
    m := m shl 1;
  end;
  Mnoz := w;
end;

// Funkcja generatora LCG
//-----------------------
function LCG() : qword;
begin
  X0  := Mnoz(X0,a,m);
  X0  := (X0 + c) mod m;
  LCG := X0;
end;

var
  Wxy,Lxy,x,y : qword;
  i,n : integer;
  XR  : double;
begin
  Uprzypadkowij;
  readln(x,y,n);
  Lxy := y - x + 1;
  for i := 1 to n do
  begin
    XR  := LCG / m;
    Wxy := trunc(XR * Lxy) + x;
    write(Wxy,' ');
  end;
  writeln;
end.
Code::Blocks
// Liczby pseudolosowe w <x,y>
// Data   : 12.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>
#include <cmath>

using namespace std;

typedef unsigned long long ulong;

// Zmienne globalne dla LCG
//-------------------------

const ulong a = 3141592653ull;
const ulong c = 2718281829ull;
const ulong m = 34359738368ull;

ulong X0;

// Procedura inicjuje ziarno X
//----------------------------
void Uprzypadkowij()
{
  X0 = (ulong)time(NULL);
}

// Funkcja oblicza a * b mod n
//----------------------------
ulong Mnoz(ulong a, ulong b, ulong n)
{
  ulong m,w;

  w = 0; m = 1;
  while(m)
  {
    if(b & m) w = (w + a) % n;
    a = (a << 1) % n;
    m <<= 1;
  }
  return w;
}

// Funkcja generatora LCG
//-----------------------
ulong LCG()
{
  X0  = Mnoz(X0,a,m);
  X0  = (X0 + c) % m;
  return X0;
}

int main()
{
  ulong Wxy,Lxy,x,y;
  int n;
  double XR;

  Uprzypadkowij();
  cin >> x >> y >> n;
  Lxy = y - x + 1;
  for(int i = 1; i <= n; i++)
  {
    XR  = LCG() / (double)m;  
    Wxy = (ulong)floor(XR * Lxy) + x;
    cout << Wxy << " ";
  }
  cout << endl << endl;
  return 0;
}
Free Basic
' Liczby pseudolosowe w <x,y>
' Data   : 12.04.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

' Zmienne globalne dla LCG
'-------------------------
Dim Shared a As ULongInt = 3141592653
Dim shared c As ULongInt = 2718281829
Dim Shared m As ULongInt = 34359738368

Dim Shared X0 As Ulongint

' Procedura inicjuje ziarno X
'----------------------------
Sub Uprzypadkowij()
  X0 = Culngint(Timer * 1000) Mod m
End Sub

' Funkcja oblicza a * b mod n
'----------------------------
Function Mnoz(Byval ax As Ulongint, Byval bx As Ulongint, Byval n As Ulongint) As Ulongint

  Dim As Ulongint mx,w

  w = 0: mx = 1
  While mx
    If bx And mx Then w = (w + ax) Mod n
    ax = (ax Shl 1) Mod n
    mx = mx Shl 1
  Wend
  Mnoz = w
End Function

' Funkcja generatora LCG
'-----------------------
Function LCG() As Ulongint
  X0  = Mnoz(X0,a,m)
  X0  = (X0 + c) Mod m
  LCG = X0
End Function

' Zaokrągla w dół
'----------------
Function Floor(Byval x As Double) As Ulongint
   Dim result As Ulongint
   result = Culngint(x)
   If result > x Then result -= 1
   Floor = result
End Function

Dim As Ulongint Wxy,Lxy,x,y
Dim As Integer i,n
Dim As Double XR

Uprzypadkowij()
Input x,y,n
Lxy = y - x + 1
For i = 1 To n
  LCG()
  XR  = X0 / m
  Wxy = Floor(XR * Lxy) + x
  Print Wxy;" ";
Next
Print
End
Wynik
1 6 40
4 5 4 2 4 6 2 4 4 3 6 5 1 5 2 3 6 5 6 1 5 5 5 3 4 2 2 6 3 6 5 6 2 5 3 5 4 1 4 3

1 6 40
3 1 5 1 3 4 5 1 5 2 4 5 6 3 5 2 5 2 3 6 2 1 3 1 2 3 4 5 4 2 3 6 2 2 3 4 3 5 4 2

1 6 40
3 3 2 1 5 2 1 2 5 5 4 3 1 5 5 3 3 6 5 1 3 5 1 6 6 6 4 2 4 2 4 5 2 4 6 3 1 4 2 2

 

Liczby pseudolosowe w przedziale <x,y>
(C)2012 mgr Jerzy Wałaszek

x = , y = , n =


...

 



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.