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

©2024 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 {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żane 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:

 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 = (a×Xn-1+c) mod m
Multiplikatywny LCG:
Xn = a×Xn-1 mod m

Zasadnicza 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…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,X0)
m = 34359738368 = 235
a = [π × 109]
c = [e × 109],
e – podstawa logarytmów naturalnych,
e = 2,718281828459…

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 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 pętli 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
Python (dodatek)
# Generator LCG
# Data   : 15.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

arr = input().split(" ")
m = int(arr[0])
a = int(arr[1])
c = int(arr[2])
x0 = int(arr[3])
x = x0
while True:
    x = (a*x+c) % m
    print(x,end=" ")
    if x == x0: break
print()
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 =
X0 =


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 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.
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 <ctime>

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(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 *= d
    Do
      x \= d
    Loop Until x Mod d <> 0
  End If
  If d = 2 Then
    d += 1
  Else
    d += 2
  End If
  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
Python (dodatek)
# Współczynniki generatora LCG
# Data   : 15.02.2024
# (C)2024 mgr Jerzy Wałaszek
# ---------------------------

import math
import random


def nwd(a,b):
    while b:
        t = b
        b = a % b
        a = t
    return a

x = int(input())
m = x+1
while True:
    c = random.randrange(0,m)
    if nwd(m,c) == 1: break
a,x,d = 1,m,2
g = int(math.sqrt(m))
while d <= g:
    if not (x % d):
        a *= d
        while True:
            x //= d
            if x % d: break
    if d == 2:
        d += 1
    else:
        d += 2
    if x < d: break
a *= x
if not (m % 4): a <<= 1
a += 1
print("m = %12d" % m)
print("a = %12d" % a)
print("c = %12d" % c)
Wynik:
9987
m =         9988
a =         9989
c =         1785

Współczynniki dla generator LCG
(C)2020 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ą.
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"; // Oceniamy generator
     else cout << "---";
     delete [] T;              // Usuwamy tablicę dynamiczną
     cout << endl << endl;
  }
  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
Python (dodatek)
# Test generatora LCG
# Data   : 15.02.2024
# (C)2024 mgr Jerzy Wałaszek
# ---------------------------

while True:
    m = int(input("m = "))  # Czytamy moduł
    if not m: break         # Jeśli zero, to kończymy
    a = int(input("a = "))  # Czytamy mnożnik
    c = int(input("c = "))  # Czytamy przyrost
    t = [False] * m         # Tworzymy tablicę dynamiczną
    x = 0  # Określamy ziarno generatora
    for i in range(m):      # 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 in range(m):
        if t[i]: count += 1 # Zliczamy wygenerowane liczby
    print(count)            # Wyświetlamy ilość wygenerowanych liczb
    if count == m:          # Oceniamy generator
        print("OK")
    else:
        print("---")
        print()
    del t                   # Usuwamy tablicę dynamiczną
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 = 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
 

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 = 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:

Lxy ← y-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):

XR ← X: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ą ; w pętli generujemy pożądaną ilość liczb pseudolosowych
     liczbę razy kroki K03…K07
K03:   X  ← (a × X + c) mod m ; generujemy liczbę pseudolosową
K04:   XRX : m ; tworzymy rzeczywistą liczbę pseudolosową
K05:   Lxyy - x  + 1 ; obliczamy długość przedziału <x,y> plus 1
K06:   Wxy ← floor(XR × Lxy) + x ; obliczamy liczbę pseudolosową w <x,y>
K07:   Przetwarzaj Wxy ; 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, 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.

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
Python (dodatek)
# Liczby pseudolosowe w <x,y>
# Data   : 15.03.2024
# (C)2024 mgr Jerzy Wałaszek
# ---------------------------

import time

# Zmienne globalne dla LCG
# -------------------------
A = 3141592653
C = 2718281829
M = 34359738368
X0 = 0
G = 2**64

# Procedura inicjuje ziarno X
# ----------------------------
def uprzypadkowij():
    global X0
    X0 = int(time.time()) % M
    return

# Funkcja oblicza a*b mod n
# -------------------------
def mnoz(ax,bx,n):
    w,mx = 0,1
    while mx < G:
        if bx & mx:
            w = (w+ax) % n
        ax = (ax << 1) % n
        mx <<= 1
    return w

# Funkcja generatora LCG
# -----------------------
def lcg():
    global X0
    X0 = mnoz(X0,A,M)
    X0 = (X0+C) % M
    return X0

# Zaokrągla w dół
# ----------------
def floor(x):
    r = int(x)
    if r > x: r -= 1
    return r

uprzypadkowij()
arr = input().split(" ")
x = int(arr[0])
y = int(arr[1])
n = int(arr[2])
lxy = y - x + 1
for i in range(n):
    lcg()
    xr = X0 / M
    wxy = floor(xr * lxy) + x
    print(wxy, end=" ")
print()
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
©2024 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.