eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingtesty krzyżowe generatorów liczb losowych
Ilość wypowiedzi w tym wątku: 3

  • 1. Data: 2017-12-24 08:32:56
    Temat: testy krzyżowe generatorów liczb losowych
    Od: "M.M." <m...@g...com>

    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



















  • 2. Data: 2017-12-24 13:50:25
    Temat: Re: testy krzyżowe generatorów liczb losowych
    Od: "M.M." <m...@g...com>

    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


  • 3. Data: 2017-12-26 02:38:58
    Temat: Re: testy krzyżowe generatorów liczb losowych
    Od: "M.M." <m...@g...com>

    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





strony : [ 1 ]


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: