eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingtesty krzyżowe generatorów liczb losowych › testy krzyżowe generatorów liczb losowych
  • X-Received: by 10.31.171.73 with SMTP id u70mr1744399vke.10.1514100776378; Sat, 23
    Dec 2017 23:32:56 -0800 (PST)
    X-Received: by 10.31.171.73 with SMTP id u70mr1744399vke.10.1514100776378; Sat, 23
    Dec 2017 23:32:56 -0800 (PST)
    Path: news-archive.icm.edu.pl!news.icm.edu.pl!news.nask.pl!news.nask.org.pl!news.unit
    0.net!weretis.net!feeder6.news.weretis.net!feeder.usenetexpress.com!feeder-in1.
    iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!border2.nntp.dca1.giganew
    s.com!nntp.giganews.com!g35no1243792qtk.1!news-out.google.com!t48ni467qtc.1!nnt
    p.google.com!m31no1244305qtf.0!postnews.google.com!glegroupsg2000goo.googlegrou
    ps.com!not-for-mail
    Newsgroups: pl.comp.programming
    Date: Sat, 23 Dec 2017 23:32:56 -0800 (PST)
    Complaints-To: g...@g...com
    Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=159.205.159.4;
    posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
    NNTP-Posting-Host: 159.205.159.4
    User-Agent: G2/1.0
    MIME-Version: 1.0
    Message-ID: <f...@g...com>
    Subject: testy krzyżowe generatorów liczb losowych
    From: "M.M." <m...@g...com>
    Injection-Date: Sun, 24 Dec 2017 07:32:56 +0000
    Content-Type: text/plain; charset="UTF-8"
    Content-Transfer-Encoding: quoted-printable
    Lines: 139
    Xref: news-archive.icm.edu.pl pl.comp.programming:212028
    [ ukryj nagłówki ]

    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


















Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

  • 24.12.17 13:50 M.M.
  • 26.12.17 02:38 M.M.

Najnowsze wątki z tej grupy


Najnowsze wątki

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: