Generator pseudolosowy Parka-Millera


Tematy pokrewne
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 Parka-Millera
Generator pseudolosowy Mersenne Twister
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Liczby Fibonacciego
System liczbowy Fibonacciego
Całkowity pierwiastek kwadratowy

 

Generator pseudolosowy Park-Miller jest odmianą multiplikatywnego liniowego generatora kongruencyjnego. Ogólny wzór generacyjny ma poniższą postać:

 

Xi = Xi-1 × g mod n

Gdzie:

Xi  –  generowana, nowa liczba pseudolosowa
Xi-1  – poprzednio wygenerowana liczba pseudolosowa
g  – pierwiastek pierwotny modulo n
n  – liczba pierwsza lub jej potęga
X0  – ziarno pseudolosowe musi być względnie pierwsze z n

 

Pierwiastek pierwotny modulo n (ang. primitive root modulo n) jest dowolną liczbą g o własności takiej, iż każda liczba względnie pierwsza z n przystaje do do pewnej potęgi g modulo n. Innymi słowy, jeśli g jest pierwiastkiem pierwotnym modulo n i NWD(a,n) = 1, to istnieje taka liczba całkowita k, iż gk mod n = a.

Generator P-M posiada okres powtarzania równy n-1. Można go traktować jako szczególny przypadek multiplikatywnego generatora LCG, jednakże współczynniki g i n oraz X0 muszą spełniać powyżej podane warunki. Oto kilka par wartości n i g, które są stosowane w praktyce:

 

Lp. n g
1 216+1=65537 (liczba pierwsza Fermata F4) 75 (pierwiastek pierwotny modulo F4)
2 231-1 = 2147483647 (liczba pierwsza Mersenne'a M31) 16807 (pierwiastek pierwotny modulo M31)
3 248 = 281474976710656 44485709377909
4 4294967291 279470273

 

Wykorzystując pozycję nr 2, tj. n = 231-1 i g = 16807, można skonstruować generator LCG, w którym operację mnożenia modulo n zastąpimy prostymi działaniami na bitach. Ma to sens dla małych mikroprocesorów, np. kontrolerów jednoukładowych, w których albo brak jest operacji dzielenia z resztą, albo jest ona kosztowna czasowo.

 

Algorytm generatora pseudolosowego Park-Miller

Wejście
X0    ziarno pseudolosowe
Wyjście:

X0 – liczba pseudolosowa z zakresu od 1 do 231 - 1.

Zmienne pomocnicze
XLO    dolna połówka iloczynu
XHI  – górna połówka iloczynu
Lista kroków:
K01: XLO ← 16807 × (X0 and $FFFF) ; obliczamy dolną połówkę iloczynu
K02: XHI ← 16807 × (X0 shr 16) ; obliczamy górną połówkę iloczynu
K03: XLOXLO +  ((XHI and $7FFF) shl 16) ; łączymy dolną połówkę z górną
K04: XLOXLO + (XHI shr 15)  
K05: Jeśli XLO > $7FFFFFFF, to XLOXLO - $7FFFFFFF ; korekcja wyniku
K07: X0XLO ; wynik zapamiętujemy w ziarnie
K08: Zakończ z wynikiem 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.

 

Program odczytuje z pierwszego wiersza trzy liczby a,b oraz n. Liczby a i b określają przedział całkowity, w którym mają być wygenerowane liczby pseudolosowe. Liczba n określa ile liczb pseudolosowych należy wygenerować. Liczby pseudolosowe są generowane w kolejnych wierszach. Ponieważ okres n jest liczbą pierwszą, to każda liczba X0 mniejsza od n i większa od 0 jest względnie pierwsza z n i może być użyta na ziarno pseudolosowe. X0 inicjujemy wartością odczytaną z zegara systemowego.

 

Lazarus
// Generator pseudolosowy Park-Miller
// Data:   18.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------------

program prg;

uses SysUtils,DateUtils;

var x0 : longword;

// Generuje liczby pseudolosowe
//-----------------------------
function PM_RNG : longword;
var
  xlo,xhi : longword;
begin
  xlo := 16807 * (x0 and $ffff);
  xhi := 16807 * (x0 shr 16);
  inc(xlo,(xhi and $7fff) shl 16);
  inc(xlo,xhi shr 15);
  if xlo > $7fffffff then dec(xlo,$7fffffff);
  x0 := xlo;
  PM_RNG := xlo;
end;

// Ustawia losowe x0
//------------------
procedure Uprzypadkowij;
var
  t  : TDateTime;
begin
  repeat
    t  := Now;
    x0 := HourOf(t);
    x0 := x0 *   60 + MinuteOf(t);
    x0 := x0 *   60 + SecondOf(t);
    x0 := x0 * 1000 + MillisecondOf(t);
  until x0 <> 0;  
end;

var
  a,b,n,i : longint;
begin
  readln(a,b,n);
  Uprzypadkowij;
  for i := 1 to n do write(a + PM_RNG mod (b - a + 1),' ');
  writeln;
end.
Code::Blocks
// Generator pseudolosowy Park-Miller
// Data:   18.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------------

#include <iostream>

using namespace std;

unsigned int x0;

// Generuje liczby pseudolosowe
//-----------------------------
unsigned int PM_RNG()
{
  unsigned int xlo,xhi;

  xlo = 16807 * (x0 & 0xffff);
  xhi = 16807 * (x0 >> 16);
  xlo += (xhi & 0x7fff) << 16;
  xlo += xhi >> 15;
  if(xlo > 0x7fffffff) xlo -= 0x7fffffff;
  return (x0 = xlo);
}

// Ustawia losowe x0
//------------------
void Uprzypadkowij()
{
  do x0 = (unsigned int) time(NULL); while(!x0);
}

int main()
{
  unsigned int a,b,n,i;

  cin >> a >> b >> n;
  Uprzypadkowij();
  for(i = 1; i <= n; i++) cout << (a + PM_RNG() % (b - a + 1)) << " ";
  cout << endl;
  return 0;
}
Free Basic
' Generator pseudolosowy Park-Miller
' Data:   18.04.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------------

Dim Shared x0 As Uinteger

' Generuje liczby pseudolosowe
'-----------------------------
Function PM_RNG As Uinteger

  Dim As Uinteger xlo,xhi

  xlo = 16807 * (x0 And &Hffff)
  xhi = 16807 * (x0 Shr 16)
  xlo += (xhi And &H7fff) Shl 16
  xlo +=  xhi Shr 15
  If xlo > &H7fffffff Then xlo -= &H7fffffff
  x0 = xlo
  PM_RNG = xlo
End Function

' Ustawia losowe x0
'------------------
Sub Uprzypadkowij
  Do
    x0 = Timer * 1000
  Loop Until x0
End Sub

Dim As Integer a,b,n,i

Open Cons For Input As #1

Input #1,a,b,n

Close #1

Uprzypadkowij
For i = 1 To n: Print a + PM_RNG Mod (b - a + 1);: Next
Print

End
Wynik
1 6 200
3 2 1 5 2 6 2 2 2 3 2 5 4 5 2 2 6 4 3 6 6 5 3 5 5 5 3 6 5 1 6 5 3 4 1 1 1 1 3 6
2 4 2 6 3 6 3 5 1 2 6 4 4 5 1 1 3 2 4 4 6 4 6 5 1 1 6 2 4 5 5 4 3 4 2 4 6 3 6 5
1 4 3 5 5 4 6 3 5 3 2 6 5 2 4 3 6 6 6 5 4 2 1 3 1 3 5 3 1 5 4 1 2 2 3 3 6 6 5 2
4 1 3 3 4 2 6 2 6 6 2 1 5 5 2 1 4 6 4 1 4 3 2 1 4 1 4 3 3 5 3 6 2 5 5 1 4 2 3 3
1 3 4 4 1 2 3 5 5 3 1 5 2 6 6 2 1 5 3 2 6 4 6 6 2 3 4 3 4 3 3 3 6 4 4 4 5 5 1 5

 



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.