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

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

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 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,       ; korekcja wyniku
     to XLOXLO - $7FFFFFFF
K07: X0XLO                     ; wynik zapamiętujemy w ziarnie
K08: Zakończ z wynikiem 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.

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.
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
Python (dodatek)
# Generator pseudolosowy Park-Miller
# Data:   16.02.2024
# (C)2024 mgr Jerzy Wałaszek
# ---------------------------

import time

x0 = 0


# Generuje liczby pseudolosowe
# -----------------------------
def pm_rng():
    global x0
    xlo = 16807 * (x0 & 0xffff)
    xhi = 16807 * (x0 >> 16)
    xlo += (xhi & 0xfff) << 16
    xlo += xhi >> 15
    if xlo > 0x7fffffff: xlo -= 0x7fffffff
    x0 = xlo
    return xlo


# Procedura inicjuje ziarno X
# ----------------------------
def uprzypadkowij():
    global x0
    while True:
        x0 = int(time.time() * 1000)
        if x0: break
    return


arr = input().split(" ")
a = int(arr[0])
b = int(arr[1])
n = int(arr[2])
uprzypadkowij()
for i in range(n):
    print(a + pm_rng() % (b - a + 1), end=" ")
print()
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
©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.