MKZR/Liczby losowe
Z Skrypty dla studentów Ekonofizyki UPGOW
(Różnice między wersjami)
(→Generacja liczb losowych) |
(→Generacja liczb losowych) |
||
(Nie pokazano 2 wersji pomiędzy niniejszymi.) | |||
Linia 3: | Linia 3: | ||
Generator liczb pseudolosowych to procedura, generująca deterministycznie ciąg bitów, który pod pewnymi względami jest nieodróżnialny od ciągu uzyskanego z prawdziwie losowego źródła. | Generator liczb pseudolosowych to procedura, generująca deterministycznie ciąg bitów, który pod pewnymi względami jest nieodróżnialny od ciągu uzyskanego z prawdziwie losowego źródła. | ||
- | + | Najprostszym przykładem jest liniowy generator kongruencyjny (ang. Linear congruential generator, LCG), który jest wyznaczony przez relację rekurencyjną: | |
: <math>X_{n+1} = \left( a X_n + c \right)~~\bmod~~m</math> | : <math>X_{n+1} = \left( a X_n + c \right)~~\bmod~~m</math> | ||
Linia 70: | Linia 70: | ||
- | "Jedynym słusznym" generatorem używanym obecnie jest | + | "Jedynym słusznym" generatorem używanym obecnie jest [http://pl.wikipedia.org/wiki/Mersenne_Twister Mersenne Twister]. Jest on szybki i zapewnia dobre własności statystyczne generowanego ciągu liczb. W systemie GNU Octave funkcja rand używa |
Mersenne Twister-a. | Mersenne Twister-a. | ||
Aktualna wersja na dzień 20:54, 15 mar 2010
Spis treści |
Generacja liczb losowych
Generator liczb pseudolosowych to procedura, generująca deterministycznie ciąg bitów, który pod pewnymi względami jest nieodróżnialny od ciągu uzyskanego z prawdziwie losowego źródła.
Najprostszym przykładem jest liniowy generator kongruencyjny (ang. Linear congruential generator, LCG), który jest wyznaczony przez relację rekurencyjną:
- \(X_{n+1} = \left( a X_n + c \right)~~\bmod~~m\)
Jego implementacja w octave:
function y=myran(x); a=1664525; b=1013904223; m=2^32; y=mod(a*x+b,m); return; end
przykład jego użycia do generacji pseudolosowych liczb z przedziału (0,1):
x(1)=123; for i=2:10; x(i)=myran(x(i-1)); disp(x(i)/2^32); end
Generator ten ma wiele mankamentów:
- okres niskich bitów jest o wiele niższy od okresu całego generatora.
x(1)=1234; for bitn=1:10 for i=2:30; x(i)=myran(x(i-1)); printf("Bit %d: %d\n", bitn,bitget(x(i),bitn) ); end a=input('cont?','s'); if (a=='q') break; end end
- Jeżeli użyjemy LCG do generacji punktów w n-wymiarowej przestrzeni to punkty te będą leżały na \(m^{1/n}\) hiperpowierzchniach.
function y=myranbad(x); a=65539; b=0; m=2^31; y=mod(a*x+b,m); return; end
x(1)=1234; for i=2:3000; x(i)=myranbad(x(i-1)); end X=reshape(x,[3,length(x)/3]); randmax=2^31*1.0 plot3(X(1,:)/randmax,X(2,:)/randmax,X(3,:)/randmax,'*')
"Jedynym słusznym" generatorem używanym obecnie jest Mersenne Twister. Jest on szybki i zapewnia dobre własności statystyczne generowanego ciągu liczb. W systemie GNU Octave funkcja rand używa Mersenne Twister-a.