Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Liniowe generatory liczb pseudolosowych

SPIS TREŚCI
Podrozdziały

Liczby pseudolosowe

Liczba losowa ( ang. random number ) jest liczbą r  należącą do pewnego zbioru wartości { r 1, ..., r n } 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.

Na początek:  podrozdziału   strony 

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:

X n  = ( a × X n - 1 + c  ) mod 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 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ć:

X 0X 1X 2 → ...  → X m - 2  → X m - 1X 0X 1 → ...

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: X n  = ( a · X n - 1 + c  ) mod m
Multiplikatywny LCG: X n  = a · X n - 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...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 ) mod 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 0, 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 = 0 i policzmy wszystkie kolejne liczby pseudolosowe, które tworzy nasz generator LCG:

X 1 = ( 13 ×   0 + 7 ) mod 12 =  7 mod 12 =  7  
X 2 = ( 13 ×  7 + 7 ) mod 12 =  98 mod 12 =  2  
X 3 = ( 13 ×  2 + 7 ) mod 12 =  33 mod 12 =  9  
X 4 = ( 13 ×  9 + 7 ) mod 12 =  124 mod 12 =  4  
X 5 = ( 13 ×  4 + 7 ) mod 12 =  59 mod 12 =  11  
X 6 = ( 13 ×  11 + 7 ) mod 12 =  150 mod 12 =  6  
X 7 = ( 13 ×  6 + 7 ) mod 12 =  85 mod 12 =  1  
X 8 = ( 13 ×  1 + 7 ) mod 12 =  20 mod 12 =  8  
X 9 = ( 13 ×  8 + 7 ) mod 12 =  111 mod 12 =  3  
X 10 = ( 13 ×  3 + 7 ) mod 12 =  46 mod 12 =  10  
X 11 = ( 13 ×  10 + 7 ) mod 12 =  137 mod 12 =  5  
X 12 = ( 13 ×  5 + 7 ) mod 12 =  72 mod 12 =  0  
X 13 = ( 13 ×  0 + 7 ) mod 12 =  7 mod 12 =  7  = X 1 – ciąg zaczyna się powtarzać
X 14 = ( 13 ×  7 + 7 ) mod 12 =   98 mod 12 =  2  = X 2
...

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

Dla X 0 = 1 mamy : 8 3 10 5 0 7 2 9 4 11 6 1 ...
Dla X 0 = 2 mamy : 9 4 11 6 1 8 3 10 5 0 7 2 ...
Dla X 0 = 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 0 )
m  – moduł
a  – mnożnik
c  – przyrost
X 0 – 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,  X 0 )
m  = 34359738368 = 2 35
a  = [ π  × 10 9 ]
c  = [ e  × 10 9 ], e  – podstawa logarytmów naturalnych, e  = 2, 7182818284590452353602874713527...

Przykładowe programy

Uwaga:

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 X 0. 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.
Pascal
// Generator LCG
// Data   : 8.04.2008
// (C)2020 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.
   C++
// Generator LCG
// Data   : 8.04.2008
// (C)2020 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;
}
   Basic
' Generator LCG
' Data   : 8.04.2008
' (C)2020 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)2020 mgr Jerzy Wałaszek
m =
a =
c =
X 0 =

...


Przykładowe programy

Uwaga:

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 X max, 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.
Pascal
// Współczynniki generatora LCG
// Data   : 10.04.2008
// (C)2020 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.
C++
// Współczynniki generatora LCG
// Data   : 10.04.2008
// (C)2020 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;
}
Basic
' Współczynniki generatora LCG
' Data   : 10.04.2008
' (C)2020 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)2020 mgr Jerzy Wałaszek

X max =


...

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ą.
Pascal
// 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.
C++
// 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;
}
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
---
Na początek:  podrozdziału   strony 

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  = 2 k, to

X n  = ( a  × X n - 1 + c  ) mod 2 k = ( a  × X n - 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  × X n - 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 2 32 1664525 1013904223  
Borland C/C++ 2 32 22695477 1 bity 30..16 w rand( ), 30..0 w lrand( )
GNU Compiler Collection 2 32 69069 5 bity 30..16
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++ 2 32 1103515245 12345 bity 30..16
Borland Delphi, Virtual Pascal 2 32 134775813 1 bity 63..32 w ( seed * L )
Microsoft Visual/Quick C/C++ 2 32 214013 2531011 bity 30..16
ANSIC 2 31 1103515245 12345  
MINSTD 2 31-1 16807 0  
RANDU 2 31 65539 0  
SIMSCRIPT 2 31-1 630360016 0  
BCSLIB 2 35 5 15 7261067085  
BCPL 2 32 2147001325 715136305  
URN12 2 31 452807053 0  
APPLE 2 35 1220703125 0  
Super-Duper 2 32 69069 0  
Na początek:  podrozdziału   strony 

Liczby pseudolosowe w przedziale

Problem

Mając dany generator LCG, należy wygenerować ciąg 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  = 2 64. 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 2 64 ! ( 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:

L xy  ← y  - x  + 1

Liczba L xy  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  ]:

W xy  ← ( X  mod L xy  ) + 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 ):

X R  ← X  : m

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

W xy  ← [ X R  × L xy ] + x

Ponieważ teraz przy tworzeniu W xy  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, yC.
LCG ( m, a, c  )  – generator LCG.

Wyjście:

W xy  liczba pseudolosowa z przedziału [ x, y ].

Zmienne pomocnicze:

Lxy  –  długość przedziału [ x, y  ] + 1.
X  – ziarno pseudolosowe oraz liczba pseudolosowa.
X R  – 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:     X R  ← X  : m tworzymy rzeczywistą liczbę pseudolosową
K05:     L xy  ← y  - x  + 1 obliczamy długość przedziału [ x, y ] plus 1
K06:     W xy  ←  floor( X R  × L xy ) + x obliczamy liczbę pseudolosową w [ x, y ]
K07:     Przetwarzaj W xy wykorzystujemy wygenerowaną liczbę pseudolosową
K08: Zakończ  

Przykładowe programy

Uwaga:

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,  X o )

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.

Pascal
// Liczby pseudolosowe w <x, y>
// Data   : 12.04.2008
// (C)2020 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.
C++
// Liczby pseudolosowe w <x, y>
// Data   : 12.04.2008
// (C)2020 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;
}
Basic
' Liczby pseudolosowe w <x, y>
' Data   : 12.04.2008
' (C)2020 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)2020 mgr Jerzy Wałaszek
x =
y =
n =

...

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

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.