|
Serwis Edukacyjny w I-LO w Tarnowie
Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2026 mgr Jerzy Wałaszek
|
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
n : liczba pierwsza lub jej potęga.
X0 : ziarno pseudolosowe musi być względnie pierwsze
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
Generator P-M posiada okres powtarzania równy
| 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.
K01: XLO ← 16807×(X0 and $FFFF) ; obliczamy dolną połówkę iloczynu K02: XHI ← 16807×(X0 shr 16) ; obliczamy górną połówkę iloczynu K03: XLO ← XLO+((XHI and $7FFF) shl 16) ; łączymy dolną połówkę z górną K04: XLO ← XLO+(XHI shr 15) K05: Jeśli XLO > $7FFFFFFF, ; korekcja wyniku to XLO ← XLO-$7FFFFFFF K07: X0 ← XLO ; wynik zapamiętujemy w ziarnie K08: Zakończ z wynikiem X0
|
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. |
// 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 |
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2026 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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.