Najpierw link do źródła:
https://pastebin.com/9gNn76rk


Potem link do tabelek z wynikami (z dwóch uruchomień dla innych zarodków):
https://pastebin.com/tXyMMiE0

Pod tabelkami widać, że testy trwały ponad 100 godzin.


Wzajemnie testowało się sześć generatorów:
typedef LinRnd Rnd0;
typedef FibRnd Rnd1;
typedef std::mt19937_64 Rnd2;
typedef std::ranlux48 Rnd3;
typedef std::minstd_rand0 Rnd4;
typedef std::minstd_rand Rnd5;

Kolejność generatorów jest taka sama ja kolejność kolumn i wierszy w
tabelkach z wynikami.



Najważniejsza linia kodu z generatora LinRnd
return x = ( x * 122949823ull + 2468776129ull) % 25191867719ull;

I najważniejsza linia kodu z generatora FibRnd
return x[c] = x[a] + x[b];

Cały kod jest w źródle. Pozostałe generatory znacie.

Generatory do samo-testowania wykorzystywały, tak samo jak poprzednio,
test urodzinowy. Rok był krótki: 2^12. Ilość urodzin mała: 2^4. Wyniki
były wrzucane do 5 kubełków.

W tabelkach nazbierało się 90 wyników. Żaden wynik nie jest
mniejszy niż 0.01, a aż 22 wyniki są większe niż 0.99. Wnioski:
chi-kwadrat często miało dużą wartość, a rzadko małą. Problem
generatorów zazwyczaj polegał na tym, że generowane rozkłady
mocno się od siebie różniły. Natomiast nie występował problem
odwrotny, czyli że generowane rozkłady były zbyt podobne do
siebie. 22 wyniki większe niż 99% zniechęcają do jakichkolwiek
dalszych badań na niezależność.


Z tabelek usuwam wyniki dwóch liniowych generatorów:
typedef std::minstd_rand0 Rnd4;
typedef std::minstd_rand Rnd5;

Zostaje 46 wyników. Tym razem tylko(?) 4 wyniki są powyżej wartości 99%.
Można pokusić się o jakieś testy na niezależność. Weźmy dwa kubełki,
jeden poniżej 0.5, drugi powyżej. W kubełku powinny być 23 elementy, jest:
10 i 36. Chi-kwadrat wynosi 14,7. Skumulowany rozkład chi wynosi 0.9998736625.
Czyli mamy zaledwie 0,013% szans, na uzyskanie takiego rozkładu przy
pomocy losowego generatora. [PS. to by można policzyć (chyba) dokładniej
przy pomocy skumulowanego rozkładu dwumianowego]

Dajmy jeszcze trzy kubełki. W pierwszym kubełku jest tylko 7 elementów, w
drugim też 7, w trzecim są aż 32 elementy. Na oko już jest podejrzane.
Test chi ma wartość zaledwie 0,00013%.

Moim zdaniem test niezaliczony. Więc także usuwam z wyników pierwszy
generator linowy:
typedef LinRnd Rnd0;


Zostają tylko 24 wyniki. Przy podziale na dwa kubełki wartość oczekiwana w
kubełku wynosi więc 12. Tymczasem mamy w pierwszym kubełku 7 elementów, a
w drugim 17. Test chi-kwadrat daje ponad 4% szans na uzyskanie takiego
rozkładu w sposób losowy - mało, ale znacznie więcej niż przed usunięciem
generatora liniowego.

Niewielki jest sens dzielenia 24 wyników na 3 kubełki, ale podzielmy.
W pierwszym kubełku mamy 4, w drugim też 4, w trzecim 16 elementów.
Test chi-kwadrat daje zaledwie 0,248% szans na uzyskanie takiego
wyniku losowym generatorem.


Jak to podsumować....

1) Na pewno widać jak na dłoni, że po odrzuceniu generatorów
liniowych test jest bardziej podobny do testu na naprawdę losowych
generatorach.

2) Problem generatorów zazwyczaj polega na tym, że dają rozkłady zbyt
różnorodne, a nie zbyt podobne do siebie.

3) Test dobrych generatorów (MT, RanLux, Fibonacci) nie do końca się
udał, bo jest zbyt mało danych. Niemniej przy podziale na dwa kubełki
mamy 4% szans na uzyskanie takiego samego wyniku generatorami naprawdę
losowymi.

4) Test urodzinowy był ułatwiony, krótki rok, mało urodzin.

Pozdrawiam

do góry

On Sunday, December 24, 2017 at 8:32:57 AM UTC+1, M.M. wrote:
> [...]

A tak swoją drogą...

Wpisałem w google walidację krzyżową generatorów liczb losowych, widzę, że
zero wyników:

https://www.google.pl/search?client=ubuntu&hs=51S&ch
annel=fs&dcr=0&ei=RqE_Ws7lG4ey6ATos5TADg&q=%22cross+
validation+random+number+generators%22&oq=%22cross+v
alidation+random+number+generators%22&gs_l=psy-ab.3.
..199009.202184.0.202447.4.4.0.0.0.0.104.356.3j1.4.0
....0...1c..64.psy-ab..0.0.0....0.LCYQ6Tj1yJA

Czyżbym przypadkiem coś całkiem nowego zrobił?

Pozdrawiam

do góry

On Sunday, December 24, 2017 at 1:50:27 PM UTC+1, M.M. wrote:
> On Sunday, December 24, 2017 at 8:32:57 AM UTC+1, M.M. wrote:
> > [...]
>
> A tak swoją drogą...
>
> Wpisałem w google walidację krzyżową generatorów liczb losowych, widzę, że
> zero wyników:
>
> https://www.google.pl/search?client=ubuntu&hs=51S&ch
annel=fs&dcr=0&ei=RqE_Ws7lG4ey6ATos5TADg&q=%22cross+
validation+random+number+generators%22&oq=%22cross+v
alidation+random+number+generators%22&gs_l=psy-ab.3.
..199009.202184.0.202447.4.4.0.0.0.0.104.356.3j1.4.0
....0...1c..64.psy-ab..0.0.0....0.LCYQ6Tj1yJA
>
> Czyżbym przypadkiem coś całkiem nowego zrobił?
>
> Pozdrawiam

Kontynuując...

Zmniejszyłem ilość pętli w jednym teście urodzinowym do 20mln. Za to wykonałem
ponad 650 testów krzyżowych trzech generatorów:

1) ranlux48
2) mt19937_64
3) fibonacci

Wynik testów podzieliłem na 5 kubełków i porównałem z rozkładem jednostajnym.
Wynik są w dolnym ciemno-pomarańczowym wierszu:

https://zapodaj.net/images/40ad831aabacd.png

Widać że jest tragedia, żadna para z tych trzech generatorów nie przechodzi
testu. Najlepiej wypadła para Fibonacci z samym sobą, ale prawdopodobieństwo
uzyskania takiego rozkładu jest i tak 10 zer po przecinku. Najwięcej zliczeń
jest w największym kubełku (od 0.8 do 1.0), więc problem znowu polega na
tym, że rozkłady za bardzo się różnią (a nie na tym, że są zbyt podobne do
siebie jak na losowe).

Wnioski takie same jak poprzednio: albo popełniam jakiś błąd, albo te
generatory nie nadają się do długotrwałych symulacji w których ważny
jest równomierny rozkład.

Cały kod jest pod poniższym linkiem:

https://pastebin.com/PPed7ESb

Eksperyment można otworzyć z zarodka 962630792.
Na jednym rdzeniu eksperyment trwał około 27 godzin.
Odpaliłem też na innych rdzeniach, ale wyników nie zsumowałem,
ponieważ, jak już pisałem, i tak wychodziło na jednym
zbiorze wyników od 10 do 30 miejsc po przecinku.

Za zasugerowanie potencjalnych błędów będę wdzięczny.

Pozdrawiam

do góry