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

Generator pseudolosowy Parka-Millera

SPIS TREŚCI

Generator pseudolosowy Park-Miller

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

X i  = X i - 1 × g  mod n

Gdzie:

X i  –  generowana, nowa liczba pseudolosowa.
X i - 1  – poprzednio wygenerowana liczba pseudolosowa.
g  – pierwiastek pierwotny modulo n.
n  – liczba pierwsza lub jej potęga.
X 0  – 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ż g k  mod n  = a.

Generator P-M posiada okres powtarzania równy - 1. Można go traktować jako szczególny przypadek multiplikatywnego generatora LCG, jednakże współczynniki g  i n  oraz X 0 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 2 16 + 1=65537 ( liczba pierwsza Fermata F 4 ) 75 ( pierwiastek pierwotny modulo F 4 )
2 2 31 - 1 = 2147483647 ( liczba pierwsza Mersenne'a M 31 ) 16807 ( pierwiastek pierwotny modulo M 31 )
3 2 48 = 281474976710656 44485709377909
4 4294967291 279470273

Wykorzystując pozycję nr 2, tj. n  = 2 31 - 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:

X 0  –  ziarno pseudolosowe.

Wyjście:

X 0 – liczba pseudolosowa z zakresu od 1 do 2 31 - 1.

Zmienne pomocnicze:

X LO  –  dolna połówka iloczynu.
X HI  – górna połówka iloczynu.

Lista kroków:

K01: X LO ← 16807 × ( X 0 and $FFFF ) obliczamy dolną połówkę iloczynu
K02: X HI ← 16807 × ( X 0 shr 16 ) obliczamy górną połówkę iloczynu
K03: X LOX LO + ( ( X HI and $7FFF ) shl 16 ) łączymy dolną połówkę z górną
K04: X LOX LO + ( X HI shr 15 )  
K05: Jeśli X LO > $7FFFFFFF, to X LOX LO - $7FFFFFFF korekcja wyniku
K07: X 0X LO wynik zapamiętujemy w ziarnie
K08: Zakończ z wynikiem 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.

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 X 0 mniejsza od n  i większa od 0 jest względnie pierwsza z n  i może być użyta na ziarno pseudolosowe. X 0 inicjujemy wartością odczytaną z zegara systemowego.
Pascal
// Generator pseudolosowy Park-Miller
// Data:   18.04.2008
// (C)2020 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.
C++
// Generator pseudolosowy Park-Miller
// Data:   18.04.2008
// (C)2020 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;
}
Basic
' Generator pseudolosowy Park-Miller
' Data:   18.04.2008
' (C)2020 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
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.