Oprogramowanie prawie wszystkich komputerów ma wbudowaną funkcję generowania ciągu liczb pseudolosowych o rozkładzie quasi-równomiernym. Jednak w przypadku modelowania statystycznego na generowanie liczb losowych nakładane są zwiększone wymagania. Jakość wyników takiego modelowania zależy bowiem bezpośrednio od jakości generatora liczb losowych o rozkładzie równomiernym liczby te są również źródłami (danymi początkowymi) do uzyskania innych zmiennych losowych o zadanym prawie dystrybucji.
Niestety idealne generatory nie istnieją, a listę ich znanych właściwości uzupełnia lista wad. Prowadzi to do ryzyka użycia złego generatora w eksperymencie komputerowym. Dlatego przed przeprowadzeniem eksperymentu komputerowego konieczna jest albo ocena jakości wbudowanej w komputer funkcji generowania liczb losowych, albo wybór odpowiedniego algorytmu generowania liczb losowych.
Do zastosowania w fizyce obliczeniowej generator musi mieć następujące właściwości:
Wydajność obliczeniowa to najmniejszy możliwy czas obliczeń dla następnego cyklu oraz ilość pamięci potrzebnej do pracy generatora.
Duża długość L losowa sekwencja liczb. Okres ten musi obejmować co najmniej zestaw liczb losowych niezbędnych do przeprowadzenia eksperymentu statystycznego. Ponadto nawet zbliżenie się do końca L jest niebezpieczne, co może prowadzić do błędnych wyników eksperymentu statystycznego.
Kryterium wystarczającej długości sekwencji pseudolosowej wybiera się z następujących rozważań. Metoda Monte Carlo polega na wielokrotnym powtarzaniu obliczeń parametrów wyjściowych symulowanego układu, na który wpływają parametry wejściowe oscylujące z zadanymi prawami rozkładu. Podstawą implementacji metody jest generowanie liczb losowych z mundur rozkład w przedziale , z którego tworzone są liczby losowe o danych prawach rozkładu. Następnie obliczane jest prawdopodobieństwo wystąpienia symulowanego zdarzenia jako stosunek liczby powtórzeń eksperymentów modelowych z wynikiem pozytywnym do całkowitej liczby powtórzeń eksperymentów przy danych warunkach początkowych (parametrach) modelu.
Dla wiarygodnego, w sensie statystycznym, obliczenia tego prawdopodobieństwa liczbę powtórzeń eksperymentu można oszacować ze wzoru:
Gdzie 
- funkcja odwrotna do funkcji rozkładu normalnego, 
- ufność prawdopodobieństwa błędu 
pomiary prawdopodobieństwa.
Dlatego, aby błąd nie wyszedł poza przedział ufności z ufnością np \u003d 0,95 konieczne jest, aby liczba powtórzeń eksperymentu była nie mniejsza:
(2.2)
Na przykład dla błędu 10% (
=0,1) otrzymujemy 
i dla błędu 3% (
=0,03) już otrzymaliśmy 
.
Dla innych warunków początkowych modelu należy przeprowadzić nową serię powtórzeń eksperymentów na innej sekwencji pseudolosowej. Dlatego albo funkcja generowania sekwencji pseudolosowych musi mieć parametr, który ją zmienia (na przykład R 0 ) lub jego długość musi wynosić co najmniej:
Gdzie k - liczba warunków początkowych (punkty na krzywej wyznaczone metodą Monte Carlo), N - liczba powtórzeń eksperymentu modelowego w danych warunkach początkowych, Ł jest długością sekwencji pseudolosowej.
Następnie każda seria N powtórzenia każdego eksperymentu zostaną przeprowadzone na jego segmencie sekwencji pseudolosowej.
odtwarzalność. Jak wspomniano powyżej, pożądane jest posiadanie parametru, który zmienia generowanie liczb pseudolosowych. Zwykle jest to r 0 . Dlatego bardzo ważna jest zmiana 0 nie zepsuł jakości (tj. parametrów statystycznych) generatora liczb losowych.
Dobre właściwości statystyczne. Jest to najważniejszy wskaźnik jakości generatora liczb losowych. Nie można go jednak ocenić za pomocą żadnego pojedynczego kryterium ani testu, ponieważ nie ma koniecznych i wystarczających kryteriów losowości skończonego ciągu liczb. Najwięcej, co można powiedzieć o pseudolosowej sekwencji liczb, to to, że „wygląda” losowo. Żaden pojedynczy test statystyczny nie jest wiarygodnym wskaźnikiem dokładności. Konieczne jest co najmniej zastosowanie kilku testów odzwierciedlających najważniejsze aspekty jakości generatora liczb losowych, tj. stopień jego przybliżenia do idealnego generatora.
Dlatego oprócz testowania generatora niezwykle ważne jest sprawdzenie go przy pomocy typowych problemów, które pozwalają na samodzielną ocenę wyników metodami analitycznymi lub numerycznymi.
Można powiedzieć, że idea wiarygodności liczb pseudolosowych powstaje w procesie ich używania z dokładnym sprawdzeniem wyników, kiedy tylko jest to możliwe.
Należy zauważyć, że w idealnym przypadku krzywa gęstości rozkładu liczb losowych wyglądałaby tak, jak pokazano na ryc. 22.3. Oznacza to, że w idealnym przypadku taka sama liczba punktów mieści się w każdym przedziale: N I = N/k , Gdzie Nłączna liczba punktów, k liczba interwałów, I= 1, ½, k .
generowany teoretycznie przez idealny generator
Należy pamiętać, że generowanie dowolnej liczby losowej składa się z dwóch etapów:
- generowanie znormalizowanej liczby losowej (to znaczy równomiernie rozłożonej od 0 do 1);
- transformacja znormalizowanych liczb losowych R I na liczby losowe X I, które są dystrybuowane zgodnie z (arbitralnym) prawem dystrybucji wymaganym przez użytkownika lub w wymaganym interwale.
Generatory liczb losowych według metody otrzymywania liczb dzielą się na:
- fizyczny;
- tabelaryczny;
- algorytmiczny.
Fizyczne RNG
Przykładami fizycznych RNG są: moneta („orzeł” 1, „reszka” 0); kostka do gry; bęben ze strzałą podzielony na sektory z numerami; sprzętowy generator szumów (GS), który jest używany jako hałaśliwe urządzenie termiczne, na przykład tranzystor (ryc. 22.422.5).
| Zadanie „Generowanie liczb losowych za pomocą monety” | |
|
Wygeneruj losową 3-cyfrową liczbę równomiernie rozłożoną między 0 a 1 za pomocą monety. Dokładność do trzech miejsc po przecinku. |
|
Pierwszy sposób rozwiązania problemu
Narysuj przedział od 0 do 1. Odczytując cyfry kolejno od lewej do prawej, podziel przedział na pół i za każdym razem wybierz jedną z części następnego przedziału (jeśli wypadło 0, to w lewo, jeśli wypadło 1, to Prawidłowy). W ten sposób możesz dotrzeć do dowolnego punktu w przedziale, dowolnie dokładnie. Więc, 1 : przedział jest podzielony na pół przez i , wybrana jest prawa połowa, przedział się zawęża: . Następny numer 0 : przedział jest podzielony na pół przez i , wybrana jest lewa połowa, przedział się zawęża: . Następny numer 0 : przedział jest podzielony na pół przez i , wybrana jest lewa połowa, przedział się zawęża: . Następny numer 1 : przedział jest podzielony na pół przez i , wybrana jest prawa połowa, przedział się zawęża: . Zgodnie z warunkiem dokładności problemu, rozwiązanie zostaje znalezione: jest to dowolna liczba z przedziału , na przykład 0,625. W zasadzie, jeśli podchodzimy ściśle, to podział przedziałów musi być kontynuowany, aż lewa i prawa granica znalezionego przedziału nie będą DOPASOWANE do siebie z dokładnością do trzeciego miejsca po przecinku. Oznacza to, że pod względem dokładności wygenerowana liczba nie będzie już odróżnialna od żadnej liczby z przedziału, w którym się znajduje.
Drugi sposób rozwiązania problemu
|
Tabelaryczny RNG
Tabelaryczne RNG jako źródło liczb losowych wykorzystują specjalnie zestawione tabele zawierające zweryfikowane nieskorelowane, czyli liczby, które w żaden sposób od siebie nie zależą. w tabeli. 22.1 pokazuje mały fragment takiej tabeli. Chodząc po stole od lewej do prawej, od góry do dołu, możesz uzyskać losowe liczby równomiernie rozłożone od 0 do 1 z żądaną liczbą miejsc po przecinku (w naszym przykładzie używamy trzech miejsc po przecinku dla każdej liczby). Ponieważ liczby w tabeli nie zależą od siebie, można przeglądać tabelę na różne sposoby, na przykład od góry do dołu lub od prawej do lewej, lub, powiedzmy, możesz wybrać liczby, które są na parzystych pozycjach.
| Tabela 22.1. Losowe liczby. Równomiernie rozłożone od 0 do 1 liczb losowych |
||||||||||||||||||||||||||||||||||||||||||||
| losowe liczby | równomiernie 0 do 1 liczb losowych |
|||||||
| 9 | 2 | 9 | 2 | 0 | 4 | 2 | 6 | 0.929 |
| 9 | 5 | 7 | 3 | 4 | 9 | 0 | 3 | 0.204 |
| 5 | 9 | 1 | 6 | 6 | 5 | 7 | 6 | 0.269 |
Zaletą tej metody jest to, że daje prawdziwie losowe liczby, ponieważ tabela zawiera zweryfikowane liczby nieskorelowane. Wady metody: do zapisania dużej liczby cyfr potrzeba dużo pamięci; duże trudności w generowaniu i sprawdzaniu takich tablic, powtórzenia przy korzystaniu z tablicy nie gwarantują już losowości ciągu numerycznego, a co za tym idzie wiarygodności wyniku.
Znajduje się tam tabela zawierająca 500 absolutnie losowych zweryfikowanych liczb (zaczerpnięta z książki I. G. Venetsky'ego, V. I. Venetskaya „Podstawowe pojęcia matematyczne i statystyczne oraz wzory w analizie ekonomicznej”).
Algorytmiczne RNG
Liczby generowane za pomocą tych RNG są zawsze pseudolosowe (lub quasi-losowe), to znaczy każda kolejna wygenerowana liczba zależy od poprzedniej:
R I + 1 = F(R I) .
Sekwencje złożone z takich liczb tworzą pętle, to znaczy koniecznie istnieje cykl, który powtarza się nieskończoną liczbę razy. Powtarzające się cykle nazywane są okresami.
Zaletą danych RNG jest szybkość; generatory praktycznie nie wymagają zasobów pamięci, są kompaktowe. Wady: liczb nie można w pełni nazwać losowymi, ponieważ istnieje między nimi zależność, a także obecność okresów w sekwencji liczb quasi-losowych.
Rozważ kilka algorytmicznych metod uzyskiwania RNG:
- metoda środkowych kwadratów;
- metoda produktów pośrednich;
- metoda mieszania;
- liniowa metoda kongruentna.
Metoda średniokwadratowa
Jest jakaś czterocyfrowa liczba R 0 . Ta liczba jest podnoszona do kwadratu i wprowadzana R 1. Pochodzi z R 1 w środku (cztery środkowe cyfry) pobierana jest nowa liczba losowa i zapisywana R 0 . Następnie procedura jest powtarzana (patrz ryc. 22.6). Zauważ, że w rzeczywistości jako liczbę losową należy wziąć nie ghij, A 0.ghij z zerem i kropką dziesiętną dodaną po lewej stronie. Fakt ten znajduje odzwierciedlenie na ryc. 22.6 i na kolejnych podobnych rysunkach.
 |
Wady metody: 1) jeśli w pewnej iteracji liczba R 0 staje się zerem, wówczas generator ulega degeneracji, dlatego ważny jest właściwy wybór wartości początkowej R 0; 2) generator powtórzy sekwencję M N kroki (w najlepszym razie), gdzie N długość słowa R 0 , M podstawa systemu liczbowego.
Dla przykładu na ryc. 22,6 : jeśli liczba R 0 będzie reprezentowane w systemie liczb binarnych, następnie sekwencja liczb pseudolosowych powtórzy się po 2 4 = 16 krokach. Zwróć uwagę, że powtórzenie sekwencji może nastąpić nawet wcześniej, jeśli początkowa liczba zostanie wybrana bezskutecznie.
Opisana powyżej metoda została zaproponowana przez Johna von Neumanna i pochodzi z 1946 roku. Ponieważ metoda ta okazała się zawodna, szybko z niej zrezygnowano.
Metoda produktów medianowych
Numer R 0 pomnożone przez R 1, od wyniku R 2 środek jest usunięty R 2 * (to kolejna liczba losowa) i pomnożona przez R 1. Zgodnie z tym schematem obliczane są wszystkie kolejne liczby losowe (patrz ryc. 22.7).
 |
Metoda mieszania
Metoda tasowania wykorzystuje operacje do obracania zawartości komórki w lewo iw prawo. Idea metody jest następująca. Niech komórka zapisze numer początkowy R 0 . Cyklicznie przesuwając zawartość komórki w lewo o 1/4 długości komórki otrzymujemy nową liczbę R 0*. Podobnie poprzez cykliczne przesuwanie zawartości komórki R 0 w prawo o 1/4 długości komórki, otrzymujemy drugą liczbę R 0**. Suma liczb R 0 * i R 0** daje nową liczbę losową R 1. Dalej R 1 zostaje wpisany R 0 , a cała sekwencja operacji jest powtarzana (patrz ryc. 22.8).
 |
Zauważ, że liczba wynikająca z sumowania R 0 * i R 0 ** , może nie mieścić się całkowicie w komórce R 1. W takim przypadku dodatkowe cyfry należy odrzucić z otrzymanego numeru. Wyjaśnijmy to dla rys. 22.8, gdzie wszystkie komórki są reprezentowane przez osiem cyfr binarnych. Pozwalać R 0 * = 10010001 2 = 145 10 , R 0 ** = 10100001 2 = 161 10 , Następnie R 0 * + R 0 ** = 100110010 2 = 306 10 . Jak widać liczba 306 zajmuje 9 cyfr (w systemie dwójkowym), a komórka R 1 (a także R 0 ) może pomieścić maksymalnie 8 bitów. Dlatego przed wprowadzeniem wartości w R 1 należy usunąć jeden „dodatkowy”, skrajny lewy bit z liczby 306, w wyniku czego R 1 pójdzie już nie 306, ale 00110010 2 = 50 10 . Należy również zauważyć, że w językach takich jak Pascal „obcinanie” dodatkowych bitów w przypadku przepełnienia komórki odbywa się automatycznie zgodnie z podanym typem zmiennej.
Liniowa metoda kongruentna
Liniowa metoda kongruencji jest jedną z najprostszych i obecnie najczęściej stosowanych procedur symulujących liczby losowe. Ta metoda wykorzystuje mod( X, y) , która zwraca resztę z dzielenia pierwszego argumentu przez drugi. Każda kolejna liczba losowa jest obliczana na podstawie poprzedniej liczby losowej według następującego wzoru:
R I+ 1 = mod( k · R I + B, M) .
Nazywa się ciąg liczb losowych uzyskanych za pomocą tego wzoru liniowy ciąg kongruentny. Wielu autorów odnosi się do liniowej kongruentnej sekwencji jako B = 0 multiplikatywna metoda kongruentna, i kiedy B ≠ 0 mieszana metoda kongruentna.
W przypadku generatora wysokiej jakości wymagane jest wybranie odpowiednich współczynników. Konieczne jest, aby numer M był dość duży, ponieważ okres nie może mieć więcej M elementy. Z drugiej strony dzielenie stosowane w tej metodzie jest raczej powolną operacją, więc dla komputera binarnego logicznym wyborem byłoby M = 2 N, ponieważ w tym przypadku znalezienie reszty z dzielenia jest zredukowane wewnątrz komputera do binarnej operacji logicznej „AND”. Powszechne jest również wybieranie największej liczby pierwszej M, mniej niż 2 N: w literaturze specjalistycznej udowodniono, że w tym przypadku najmniej znaczące cyfry wynikowej liczby losowej R I+ 1 zachowują się tak samo losowo jak starsze, co ma pozytywny wpływ na całą sekwencję liczb losowych jako całość. Przykładem jest jeden z Liczby Mersenne'a, równe 2 31 1 , a zatem, M= 2 31 1 .
Jednym z wymagań dla liniowych ciągów kongruentnych jest jak najdłuższy okres. Długość okresu zależy od wartości M , k I B. Przedstawione poniżej twierdzenie pozwala określić, czy możliwe jest osiągnięcie okresu o maksymalnej długości dla określonych wartości M , k I B .
Twierdzenie. Ciąg kongruentny liniowy określony przez liczby M , k , B I R 0 ma okres długości M wtedy i tylko wtedy gdy:
- liczby B I M względnie pierwsze;
- k 1 x P dla każdego prostego P, który jest dzielnikiem M ;
- k 1 jest wielokrotnością 4, jeśli M wielokrotność 4.
Na koniec zakończmy kilkoma przykładami wykorzystania liniowej metody kongruencji do generowania liczb losowych.
Stwierdzono, że seria liczb pseudolosowych wygenerowanych na podstawie danych z przykładu 1 będzie się powtarzać co roku M/4 liczby. Numer Q jest ustalany arbitralnie przed rozpoczęciem obliczeń, jednak należy mieć na uwadze, że szereg sprawia wrażenie w dużej mierze przypadkowego k(i dlatego Q). Wynik można nieco poprawić, jeśli B dziwne i k= 1 + 4 Q w takim przypadku seria będzie powtarzana co M liczby. Po długich poszukiwaniach k naukowcy ustalili wartości 69069 i 71365.
Generator liczb losowych wykorzystujący dane z przykładu 2 wygeneruje losowe liczby jednorazowe o okresie 7 milionów.
Multiplikatywna metoda generowania liczb pseudolosowych została zaproponowana przez DH Lehmera w 1949 roku.
Kontrola jakości generatora
Jakość całego systemu i dokładność wyników zależy od jakości RNG. Dlatego losowa sekwencja generowana przez RNG musi spełniać szereg kryteriów.
Przeprowadzane kontrole są dwojakiego rodzaju:
- kontrole równomiernego rozmieszczenia;
- testowanie niezależności statystycznej.
Sprawdza równomierną dystrybucję
1) RNG powinno dawać zbliżone do następujących wartości parametrów statystycznych charakterystycznych dla jednolitego prawa losowego:
2) Test częstotliwości
Test częstotliwości pozwala dowiedzieć się, ile liczb mieści się w przedziale (M R σ R ; M R + σ R) , tj. (0,5 0,2887; 0,5 + 0,2887) lub ewentualnie (0,2113; 0,7887) . Ponieważ 0,7887 0,2113 = 0,5774 wnioskujemy, że w dobrym RNG około 57,7% wszystkich losowanych liczb powinno mieścić się w tym przedziale (patrz rys. 22.9).
w przypadku sprawdzenia go do testu częstotliwości
Należy również wziąć pod uwagę, że liczba liczb w przedziale (0; 0,5) powinna być w przybliżeniu równa liczbie liczb w przedziale (0,5; 1) .
3) Test chi-kwadrat
Test chi-kwadrat (χ 2 -test) jest jednym z najbardziej znanych testów statystycznych; jest to główna metoda stosowana w połączeniu z innymi kryteriami. Test chi-kwadrat został zaproponowany w 1900 roku przez Karla Pearsona. Jego niezwykła praca jest uważana za podstawę współczesnej statystyki matematycznej.
W naszym przypadku test chi-kwadrat pozwoli nam dowiedzieć się, ile tworzymy prawdziwy RNG jest zbliżony do odniesienia RNG, tj. czy spełnia wymóg jednolitej dystrybucji, czy nie.
wykres częstotliwości odniesienie RNG pokazano na ryc. 22.10. Ponieważ prawo dystrybucji odniesienia RNG jest jednorodne, (teoretyczne) prawdopodobieństwo P I wbijanie numerów I-ty interwał (suma tych interwałów k) jest równe P I = 1/k . I tak w każdym k odstępy spadną gładki Przez P I · N liczby ( Nłączna liczba wygenerowanych numerów).
Prawdziwy RNG wygeneruje liczby rozłożone (i niekoniecznie równomiernie!) k interwały, a każdy interwał będzie zawierał N I liczby (łącznie N 1 + N 2 + ½ + N k = N ). Jak możemy określić, jak dobry i zbliżony jest testowany RNG do referencyjnego? Logiczne jest rozważenie kwadratów różnic między otrzymaną liczbą liczb N I i „odniesienie” P I · N . Dodajmy je do siebie i otrzymamy:
χ 2 dow. =( N 1 P 1 · N) 2 + (N 2 P 2 · N) 2 + + ( N k P k · N) 2 .
Z wzoru tego wynika, że im mniejsza różnica w każdym z wyrazów (a więc im mniejsza wartość χ 2 exp. ), tym silniejsze jest prawo rozkładu liczb losowych generowane przez rzeczywisty RNG, które ma tendencję do jednostajności.
W poprzednim wyrażeniu każdemu z terminów przypisano taką samą wagę (równą 1), co w rzeczywistości może nie być prawdziwe; dlatego dla statystyki chi-kwadrat konieczne jest znormalizowanie każdego z nich I wyraz, dzieląc go przez P I · N :
Na koniec napiszmy wynikowe wyrażenie bardziej zwięźle i uprośćmy je:
Otrzymaliśmy wartość testu chi-kwadrat dla eksperymentalny dane.
w tabeli. podano 22,2 teoretyczny wartości chi-kwadrat (teor. χ 2), gdzie ν = N 1 to liczba stopni swobody, P to określony przez użytkownika poziom ufności, który określa, w jakim stopniu RNG powinien spełniać wymagania jednolitej dystrybucji, lub P jest prawdopodobieństwem, że wartość eksperymentalna χ 2 exp. będzie mniejsza niż tabelaryczna (teoretyczna) teoria χ 2. lub równy temu.
| Tabela 22.2. Kilka punktów procentowych rozkładu χ 2 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| p = 1% | p = 5% | p = 25% | p = 50% | p = 75% | p = 95% | p = 99% | |
| ν = 1 | 0.00016 | 0.00393 | 0.1015 | 0.4549 | 1.323 | 3.841 | 6.635 |
| ν = 2 | 0.02010 | 0.1026 | 0.5754 | 1.386 | 2.773 | 5.991 | 9.210 |
| ν = 3 | 0.1148 | 0.3518 | 1.213 | 2.366 | 4.108 | 7.815 | 11.34 |
| ν = 4 | 0.2971 | 0.7107 | 1.923 | 3.357 | 5.385 | 9.488 | 13.28 |
| ν = 5 | 0.5543 | 1.1455 | 2.675 | 4.351 | 6.626 | 11.07 | 15.09 |
| ν = 6 | 0.8721 | 1.635 | 3.455 | 5.348 | 7.841 | 12.59 | 16.81 |
| ν = 7 | 1.239 | 2.167 | 4.255 | 6.346 | 9.037 | 14.07 | 18.48 |
| ν = 8 | 1.646 | 2.733 | 5.071 | 7.344 | 10.22 | 15.51 | 20.09 |
| ν = 9 | 2.088 | 3.325 | 5.899 | 8.343 | 11.39 | 16.92 | 21.67 |
| ν = 10 | 2.558 | 3.940 | 6.737 | 9.342 | 12.55 | 18.31 | 23.21 |
| ν = 11 | 3.053 | 4.575 | 7.584 | 10.34 | 13.70 | 19.68 | 24.72 |
| ν = 12 | 3.571 | 5.226 | 8.438 | 11.34 | 14.85 | 21.03 | 26.22 |
| ν = 15 | 5.229 | 7.261 | 11.04 | 14.34 | 18.25 | 25.00 | 30.58 |
| ν = 20 | 8.260 | 10.85 | 15.45 | 19.34 | 23.83 | 31.41 | 37.57 |
| ν = 30 | 14.95 | 18.49 | 24.48 | 29.34 | 34.80 | 43.77 | 50.89 |
| ν = 50 | 29.71 | 34.76 | 42.94 | 49.33 | 56.33 | 67.50 | 76.15 |
| ν > 30 | ν + kwadrat(2 ν ) · X P+ 2/3 X 2 P 2/3+ O(1/kwadrat( ν )) | ||||||
| X P = | 2.33 | 1,64 | 0,674 | 0.00 | 0.674 | 1.64 | 2.33 |
Rozważ akceptowalne P od 10% do 90%.
Jeśli χ 2 exp. znacznie więcej niż teoria χ2. (to jest P jest duży), a następnie generator nie satysfakcjonuje wymóg równomiernego rozkładu, ponieważ obserwowane wartości N I zbyt daleko od teorii P I · N i nie może być traktowany jako przypadkowy. Innymi słowy, ustalono tak duży przedział ufności, że ograniczenia dotyczące liczb stają się bardzo luźne, wymagania dotyczące liczb są słabe. W takim przypadku zostanie zaobserwowany bardzo duży błąd bezwzględny.
Nawet D. Knuth w swojej książce „The Art of Programming” zauważył, że mając χ 2 exp. małe też w ogóle nie jest dobre, choć na pierwszy rzut oka wydaje się niezwykłe z punktu widzenia jednorodności. Rzeczywiście, weź szereg liczb 0,1, 0,2, 0,3, 0,4, 0,5, 0,6, 0,7, 0,8, 0,9, 0,1, 0,2, 0,3, 0,4, 0,5, 0,6, są one idealne pod względem jednorodności, a χ 2 exp. będą praktycznie zerowe, ale raczej nie rozpoznasz ich jako przypadkowych.
Jeśli χ 2 exp. znacznie mniej niż teoria χ 2. (to jest P mały), a następnie generator nie satysfakcjonuje wymóg losowego rozkładu równomiernego, ponieważ obserwowane wartości N I zbyt blisko teoretycznego P I · N i nie może być traktowany jako przypadkowy.
Ale jeśli χ 2 exp. leży w pewnym przedziale, między dwiema wartościami teorii χ 2. które odpowiadają np. P= 25% i P= 50%, to możemy przyjąć, że wartości liczb losowych generowanych przez czujnik są całkowicie losowe.
Ponadto należy pamiętać, że wszystkie wartości P I · N musi być wystarczająco duża, na przykład większa niż 5 (znaleziona empirycznie). Dopiero wtedy (przy odpowiednio dużej próbie statystycznej) można uznać warunki eksperymentu za zadowalające.
Tak więc procedura weryfikacji jest następująca.
Testy niezależności statystycznej
1) Sprawdzenie częstotliwości występowania cyfry w ciągu
Rozważ przykład. Liczba losowa 0,2463389991 składa się z cyfr 2463389991, a liczba 0,5467766618 składa się z cyfr 5467766618. Łącząc ciągi cyfr otrzymujemy: 24633899915467766618.
Oczywiste jest, że teoretyczne prawdopodobieństwo P I opad I cyfra (od 0 do 9) to 0,1.
2) Sprawdzanie wyglądu serii identycznych liczb
Oznacz przez N Ł liczba serii identycznych kolejnych cyfr o długości Ł. Wszystko trzeba sprawdzić Ł od 1 do M, Gdzie M to liczba określona przez użytkownika: maksymalna liczba identycznych cyfr występujących w serii.
W przykładzie „24633899915467766618” znaleziono 2 szeregi o długości 2 (33 i 77), tj. N 2 = 2 i 2 serie długości 3 (999 i 666), tj. N 3 = 2 .
Prawdopodobieństwo serii o długości Ł jest równe: P Ł= 9 10 Ł (teoretyczny). Oznacza to, że prawdopodobieństwo wystąpienia serii o długości jednego znaku jest równe: P 1 = 0,9 (teoretycznie). Prawdopodobieństwo pojawienia się ciągu dwuznakowego wynosi: P 2 = 0,09 (teoretycznie). Prawdopodobieństwo pojawienia się ciągu trzech znaków wynosi: P 3 = 0,009 (teoretycznie).
Na przykład prawdopodobieństwo wystąpienia serii o długości jednego znaku jest równe P Ł= 0.9 , ponieważ może być tylko jeden znak na 10 i tylko 9 znaków (zero nie jest liczone). A prawdopodobieństwo, że dwa identyczne znaki „XX” spotkają się w rzędzie, wynosi 0,1 0,1 9, to znaczy prawdopodobieństwo 0,1, że znak „X” pojawi się na pierwszej pozycji, jest mnożone przez prawdopodobieństwo 0,1, że ten sam znak pojawi się na drugiej pozycji „X” i pomnożona przez liczbę takich kombinacji 9.
Częstotliwość występowania serii jest obliczana zgodnie ze wzorem „chi-kwadrat”, który wcześniej analizowaliśmy przy użyciu wartości P Ł .
Uwaga: Generator można sprawdzać wiele razy, ale kontrole nie są kompletne i nie gwarantują, że generator generuje liczby losowe. Na przykład generator, który generuje sekwencję 12345678912345, zostanie uznany za idealny podczas sprawdzania, co oczywiście nie jest do końca prawdą.
Podsumowując, zauważamy, że trzeci rozdział książki „Sztuka programowania” Donalda E. Knutha (tom 2) jest w całości poświęcony badaniu liczb losowych. Bada różne metody generowania liczb losowych, statystyczne kryteria losowości oraz transformację równomiernie rozłożonych liczb losowych na inne typy zmiennych losowych. Prezentacji tego materiału poświęcono ponad dwieście stron.
Deterministyczne PRNG
Żaden algorytm deterministyczny nie może generować liczb całkowicie losowych, może jedynie przybliżać niektóre właściwości liczb losowych. Jak powiedział John von Neumann: „ każdy, kto ma słabość do arytmetycznych metod uzyskiwania liczb losowych, jest bez wątpienia grzesznikiem».
Każdy PRNG z ograniczonymi zasobami prędzej czy później przejdzie w cykle - zaczyna powtarzać tę samą sekwencję liczb. Długość cykli PRNG zależy od samego generatora i wynosi średnio około 2 n/2 , gdzie n jest wielkością stanu wewnętrznego w bitach, chociaż generatory kongruencji liniowej i LFSR mają maksymalne cykle rzędu 2 n . Jeśli PRNG może zbiegać się w cyklach, które są zbyt krótkie, PRNG staje się przewidywalny i bezużyteczny.
Większość prostych generatorów arytmetycznych, choć szybkich, ma wiele poważnych wad:
- Zbyt krótki okres/okresy.
- Kolejne wartości nie są niezależne.
- Niektóre bity są „mniej losowe” niż inne.
- Nierównomierny rozkład jednowymiarowy.
- Odwracalność.
W szczególności algorytm mainframe okazał się bardzo słaby, co wzbudziło wątpliwości co do wiarygodności wyników wielu badań wykorzystujących ten algorytm.
PRNG ze źródłem entropii lub RNG
Wraz z potrzebą generowania łatwo odtwarzalnych sekwencji liczb losowych istnieje również potrzeba generowania liczb całkowicie nieprzewidywalnych lub po prostu całkowicie losowych. Takie generatory są nazywane generatory liczb losowych(RNG - inż. generator liczb losowych, RNG). Ponieważ takie generatory są najczęściej używane do generowania unikalnych kluczy symetrycznych i asymetrycznych do szyfrowania, są one najczęściej zbudowane z kombinacji silnego kryptograficznie PRNG i zewnętrznego źródła entropii (i ta kombinacja jest obecnie powszechnie rozumiana jako RNG).
Prawie wszyscy główni producenci mikroczipów dostarczają sprzętowe RNG z różnymi źródłami entropii, używając różnych metod, aby oczyścić je z nieuniknionej przewidywalności. Jednak w tej chwili prędkość zbierania liczb losowych przez wszystkie istniejące mikroczipy (kilka tysięcy bitów na sekundę) nie dorównuje szybkości nowoczesnych procesorów.
W komputerach osobistych twórcy oprogramowania RNG wykorzystują znacznie szybsze źródła entropii, takie jak szum karty dźwiękowej czy licznik zegara procesora. Przed możliwością odczytania wartości licznika zegara zbieranie entropii było najbardziej wrażliwym punktem RNG. Problem ten nadal nie został w pełni rozwiązany w przypadku wielu urządzeń (np. kart inteligentnych), które w związku z tym pozostają podatne na ataki. Wiele RNG nadal korzysta z tradycyjnych (przestarzałych) metod zbierania entropii, takich jak pomiar reakcji użytkownika (ruch myszy itp.), Jak na przykład, lub interakcje między wątkami, jak na przykład w Javie Secure Random.
Przykłady źródeł RNG i entropii
Kilka przykładów RNG z ich źródłami entropii i generatorami:
| Źródło entropii | PRNG | Zalety | Wady | |
|---|---|---|---|---|
| /dev/random w systemie Linux | Licznik zegara procesora, jednak zbierany tylko podczas przerwań sprzętowych | LFSR , z danymi wyjściowymi zaszyfrowanymi przez | „Nagrzewa się” bardzo długo, może „utknąć” na długi czas lub działa jak PRNG ( /dev/urandom) | |
| Krwawnik pospolity autorstwa Bruce'a Schneiera | Tradycyjne (przestarzałe) metody | AES-256 i | Elastyczna konstrukcja odporna na krypto | Długo się „nagrzewa”, bardzo mały stan wewnętrzny, za bardzo zależy od siły kryptograficznej wybranych algorytmów, wolno, ma zastosowanie tylko do generowania kluczy |
| Generator Leonid Juriew | Hałas karty dźwiękowej | ? | Prawdopodobnie dobre i szybkie źródło entropii | Brak niezależnego, znanego z silnego kryptograficznie PRNG, dostępnego wyłącznie w systemie Windows |
| Microsoftu | Wbudowany w system Windows, nie blokuje się | Mały stan wewnętrzny, łatwy do przewidzenia | ||
| Komunikacja między wątkami | W Javie nie ma jeszcze innego wyboru, duży stan wewnętrzny | Powolna kolekcja entropii | ||
| Chaos autorstwa Ruptora | Licznik zegara procesora, gromadzony w sposób ciągły | Haszowanie 4096-bitowego stanu wewnętrznego w oparciu o nieliniową wersję generatora Marsaglia | Chociaż najszybszy ze wszystkich, duży stan wewnętrzny, nie „blokuje się” | |
| RRAND firmy Ruptor | Licznik cykli procesora | Szyfrowanie stanu wewnętrznego szyfrem strumieniowym | Bardzo szybki, wewnętrzny stan o dowolnej wielkości z wyboru, nie „zacina się” |
PRNG w kryptografii
Odmianą PRNG są GPSB (PRBG) - generatory bitów pseudolosowych, a także różne szyfry strumieniowe. PRNG, podobnie jak szyfry strumieniowe, składają się ze stanu wewnętrznego (zwykle o rozmiarze od 16 bitów do kilku megabajtów), funkcji inicjującej stan wewnętrzny za pomocą klucza lub nasionko(Język angielski) nasionko), wewnętrzne funkcje aktualizacji stanu i funkcje wyjściowe. PRNG są podzielone na proste arytmetyczne, zepsute kryptograficzne i silne kryptograficzne. Ich ogólnym celem jest generowanie ciągów liczb, których metodami obliczeniowymi nie można odróżnić od przypadkowych.
Chociaż wiele silnych PRNG lub szyfrów strumieniowych oferuje znacznie więcej „losowych” liczb, takie generatory są znacznie wolniejsze niż konwencjonalne generatory arytmetyczne i mogą nie nadawać się do wszelkiego rodzaju badań, które wymagają uwolnienia procesora do bardziej użytecznych obliczeń.
Do celów wojskowych i w terenie używane są tylko tajne synchroniczne odporne na szyfrowanie PRNG (szyfry strumieniowe), szyfry blokowe nie są używane. Przykładami dobrze znanych kryptograficznie silnych PRNG są ISAAC, SEAL, Snow, bardzo powolny teoretyczny algorytm Blooma, Blooma i Shuba, a także liczniki z kryptograficznymi funkcjami mieszającymi lub kryptograficznie bezpiecznymi szyframi blokowymi zamiast funkcji wyjściowej.
PRNG sprzętu
Oprócz przestarzałych, dobrze znanych generatorów LFSR, które były szeroko stosowane jako sprzętowe PRNG w XX wieku, niestety niewiele wiadomo o nowoczesnych sprzętowych PRNG (szyfrach strumieniowych), ponieważ większość z nich została opracowana do celów wojskowych i jest utrzymywana w tajemnicy . Prawie wszystkie istniejące komercyjne PRNG sprzętu są opatentowane i również utrzymywane w tajemnicy. Sprzętowe PRNG są ograniczone ścisłymi wymaganiami dotyczącymi zużycia pamięci (najczęściej użycie pamięci jest zabronione), szybkości (1-2 cykle) i powierzchni (kilkaset FPGA - lub
Ze względu na brak dobrych sprzętowych PRNG producenci są zmuszeni używać znacznie wolniejszych, ale powszechnie znanych szyfrów blokowych (Computer Review No. 29 (2003)
Lekcja 15
Nauczyłeś już żółwia wiele. Ale ma też inne ukryte możliwości. Czy jest coś, co żółw potrafi zrobić samodzielnie, co Cię zaskoczy?
Okazuje się, że tak! Na liście czujników żółwi znajduje się generator liczb losowych:
losowy
Często spotykamy losowe liczby: rzucanie kostką w zabawie dla dzieci, słuchanie wróżki z kukułki w lesie lub po prostu „zgadywanie dowolnej liczby”. Generator liczb losowych w LogoWorlds może przyjąć wartość dowolnej dodatniej liczby całkowitej od 0 do granicy wartości określonej jako parametr.
Sama liczba, określona jako parametr generatora liczb losowych, nigdy nie odpada.
Na przykład losowa liczba 20 może być dowolną liczbą całkowitą od 0 do 19, w tym 19, losowa liczba 1000 może być dowolną liczbą całkowitą od 0 do 999, w tym 999.
Pewnie zastanawiacie się, gdzie jest gra – same liczby. Ale nie zapominaj, że w LogoWorlds za pomocą liczb możesz ustawić kształt żółwia, grubość pisaka, jego rozmiar, kolor i wiele więcej. Najważniejsze jest prawidłowe wybranie granicy wartości. Granice zmiany głównych parametrów żółwia pokazano w tabeli.
Generator liczb losowych może być używany na przykład jako parametr dowolnego polecenia do przodu, Prawidłowy i tak dalej.
Zadanie 24. Korzystanie z generatora liczb losowych
Zorganizuj jedną z poniższych gier za pomocą generatora liczb losowych i uruchom żółwia.
Gra 1: „Kolorowy ekran”
1. Umieść żółwia na środku ekranu.
2. Wpisz polecenia w plecaku i ustaw tryb Wiele razy:
nowy_kolor losowo 140 farba czekaj 10
Zespół farba wykonuje te same czynności, co narzędzie Wypełnij w edytorze graficznym.
3. Wypowiedz historię.
Gra 2: „Wesoły malarz” 1. Zmodyfikuj grę nr 1, rysując linie na ekranie w losowych obszarach z ciągłymi granicami:
2. Uzupełnij instrukcję w Turtle Backpack losowymi obrotami i ruchami:
prawy losowy 360
do przodu losowo 150
Ustaw instrukcję ruchu żółwia w Plecaku ( do przodu 60) grubym pisakiem o losowym kolorze (0-139) opuszczonym pod niewielkim kątem ( nowy_kurs 10).Gra 4: Polowanie
Opracuj fabułę, w której czerwony żółw poluje na czarnego. Czarny żółw porusza się po losowej ścieżce, podczas gdy kierunek czerwonego żółwia jest kontrolowany przez suwak.
Pytania do samokontroli
1. Co to jest generator liczb losowych?
2. Jaki jest parametr generatora liczb losowych?
3. Co oznacza granica wartości?
4. Czy sama liczba kiedykolwiek spada jako parametr?
Pierwszy algorytm uzyskiwania liczb pseudolosowych zaproponował J. Neumann. Nazywa się to metodą połowy kwadratu.
Niech będzie dana czterocyfrowa liczba R 0 =0,9876. Podnieśmy to do kwadratu. Uzyskaj 8-cyfrową liczbęR 0 2 =0,97535376. Wybieramy 4 środkowe cyfry z tej liczby i stawiamy R 1 =0,5353. Następnie ponownie podnosimy go do kwadratu i wyodrębniamy z niego 4 środkowe cyfry. Weźmy R 2 itp. Ten algorytm się nie uzasadnił. Okazało się, że więcej niż to konieczne, małe wartości R I .
Interesujące jest jednak zbadanie jakości tego generatora za pomocą przesuniętej w prawo grupy wyboru cyfr R I 2 :
gdzie a jest maksymalną wartością ułamka dla danego komputera (na przykład a = 8).
b-liczba miejsc dziesiętnych w liczbieR I(na przykład 5).
LCAŁK(A) jest częścią całkowitą liczby.
Dla a=8,b=5,R 0 \u003d 0,51111111 na PC ZX-Spectrum uzyskuje się około 1200 niepowtarzalnych liczb.
Ćwiczenia: Badanie należy przeprowadzić ze zmiennymi a, b, R 0 . Znajdź przy jakich wartościach a, b, R 0 największą długość L ciągu niepowtarzających się liczb uzyskuje się przy „dobrych” parametrach stochastycznych. Określ, czy wartość R wpływa 0 na jakość czujnika. Jeśli tak, to określ zakres „dopuszczalnych” wartości parametru R 0 . Przedstaw wyniki badań wariantu optymalnego wartości a,b,R 0 .
Algorytmy multiplikatywne. Czujnik nr 2: liniowy generator kongruencjalny Lemaire 1951.
gdzie u I,M,Cip są liczbami całkowitymi.
AmodB to reszta z dzielenia liczby całkowitej A przez B,
Mod B=A-B*INT(A/B)
Wygenerowana sekwencja ma powtarzalny cykl nieprzekraczający pnumbers.
Maksymalny okres uzyskuje się przy C0, ale taki generator daje słabe wyniki stochastyczne.
Kiedy C=0 generatory nazywamy multiplikatywnymi. Mają najlepsze parametry stochastyczne. Formuły ich użycia nazywane są również metodą dedukcyjną.
Najbardziej popularną metodą otrzymywania liczb pseudolosowych jest metoda reszt według następującego wzoru:
gdzie u I,M,p-liczby całkowite, 0
Jeśli wybierzesz U 0 i M takie, że dla R 0 =U 0 /pwynik jest ułamkiem nieredukowalnym i weźmy pM względnie pierwsze, a następnie allR I będą nierozkładalnymi ułamkami postaci: R I=U I/P.
Znajdźmy największą (ale nie większą niż p) długość niepowtarzającej się sekwencji liczb. WartościU 0 , a M jest wygodnym wyborem spośród liczb pierwszych.
Ćwiczenia: Przeglądaj w whatU 0 , a M długość sekwencji nie powtarzających się liczb będzie wynosić co najmniej 10000 przy „dobrych” parametrach stochastycznych. Określ, czy wartość R wpływa 0 z Mip=const na statystycznej charakterystyce czujnika. Jeśli tak, to określ zakres dopuszczalnych wartości U 0 . Przedstaw wyniki badań generatora dla optymalnych wartości p, Mi i U 0 .
Czujnik nr 3: Modyfikacja Korobowa.
gdzie p jest dużą liczbą pierwszą, taką jak 2027, 5087, ...
M jest liczbą całkowitą spełniającą warunki:
n jest liczbą całkowitą. Te. wybierz M bliskie p/2 ze zbioru liczb M=p– 3 n .
Na przykład dla p=5087 bierzemy n=7. Ponieważ 3 7 =2187 i 3 8 =6561 będzie więcej niż p. Zatem: M=5087-2187=2900.
Otrzymujemy liczby U I w przedziale = i liczbachR I w przedziale (0,1).
Ćwiczenia: Wybierz Mp, przy którym uzyskuje się najlepsze parametry statystyczne czujnika i największą długość L. Dowiedz się, czy wartość R wpływa 0 na charakterystykę stochastyczną czujnika, a jeśli ma to wpływ, określ zakres dopuszczalnych wartości R 0 . Przedstawić wyniki testu czujnika dla optymalnych wartości M, p i R 0 .