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 |
©2024 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 ©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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.