🚀 go-pugleaf

On 04.07.2016 21:12, Matt D. wrote:
> On 7/4/2016 20:06, M.M. wrote:
>> On Monday, July 4, 2016 at 5:57:17 PM UTC+2, M.M. wrote:
>>> On Monday, July 4, 2016 at 3:23:47 AM UTC+2, Matt D. wrote:
>>>
>>>> W praktyce: Istniejace implementacje `rand` _zdecydowanie_ zawala kazde
>>>> porzadne testy losowosci.
>>>
>>> Poprawny generator liniowy, zaimplementowany na dużym zakresie
>>> powinien przejść doskonale wszystkie testy na równomierność rozkładu,
>>> ponieważ
>>> generuje wszystkie liczby z zakresu od 0 do N-1. Moim zdaniem problem
>>> tego
>>> generatora polega na tym, że przechodzi te testy zbyt dokładnie.
>
> Byc moze, ale...
>
>>> Problemy ten generator dopiero ma przy testach na zależność, bo
>>> liczba losowa numer [i] zależy bezpośrednio od liczby [i-1].
>>> W ciut lepszych odmianach zależy od dwóch lub trzech poprzednich.
>
> ...wlasnie. I w testach losowosci w sensie ogolnym musimy miec
> zaliczenie baterii (t.j., calej kolekcji) -- zawalenie jednego implikuje
> zawalenie baterii.
>
>> Spoglądam na tę stronę z testami generatorów:
>> http://www.cacert.at/cgi-bin/rngresults
>>
>> stdlib rand() - nie przechodzi ich testów.
>> java.util.Random.Random - też nie przechodzi
>> MT19337(java)  nie przechodzi? czy to to jest merseen twister???
>> MersenneTwister19937 Gaussian - to na pewno MT, nie przechodzi???
>> Mersenne Twister (with some speed optimization) - prawie przeszedł,
>> ale tylko 6Mbajtów na sekundę.
>>
>> Czy ja czegoś nie rozumiem? MT nie przechodzi testów?
>
> Oczywiscie -- tutaj nie ma zadnego zaskoczenia, MT zdecydowanie nie
> nadaje sie do krypto --- bardziej nadaje sie do obliczen numerycznych

Tu nawet nie zbliżaamy się jeszczse do kryptograficznych PRNG,
te testy sprawdzają, jak dany generator sprawdza się w numeryce.

> (n.p., naukowe symulacje), gdzie statystyczne wlasciwosci rozkladu sa
> wazniejsze od nieprzewidywalnosci (ale tez nie jest najlepszy, to bardzo
> ciezki -- duzy stan -- i powolny generator).

Skąd ten mit o powolności MT?
On jest równie szybki jak badziewny rand.
Nie jest to jakoś super szybko, ale też trudno nazwać to
wolnym generatorem.

Duży stan przeszkadza przy próbie wsadzenia tego na GPU czy
jeśli martwimy się o cache (jak pomiędzy losowaniami mamy
dużo do roboty, to i mały stan wyleci z L1), ale najczzęścij
nie jekst to problemem. MT aktualizuje jedną komurkę stanu przy jednym
losowaniu, nie wszystkie. Jedynie co 623 (624?) losowania aktualizuje 
dodatkowo wszystkie 624 komórki.


> // Dla szybkosci (numeryka, nie krypto) to raczej
> http://www.agner.org/random/

Ciekawe. (Przydało by się uwspółcześnić, ale to tylko moje marudzenie,
bo mi range-for nie ).

Odpaliłęm i porównałem z gotowym mt z gcc.
Czasy (Ranvec1(3) , mt_199937):

0.262284 0.158556
0.282353 0.158565
0.283082 0.158531
0.283313 0.158554
0.283461 0.158525

Czasy (Ranvec1(2) , mt_199937):
0.232953 0.158655
0.252857 0.158578
0.25301 0.158577
0.25347 0.158534
0.25326 0.158584

Czasy (Ranvec1(1) , mt_199937):
0.205057 0.159159
0.196595 0.159009
0.195505 0.158919
0.196932 0.158682
0.196955 0.158765

Gotowy MT_19993 (pewnie też napisany wektorowo) jest ciut szybszy
dla float. Dla double jest lepiej:
Czasy (Ranvec1(3) , mt_199937):
0.314738 0.433556
0.310824 0.43496
0.310764 0.434656
0.310771 0.433265
0.310793 0.434174

Ranvec1 może mieć lepsze własności, dodatkowe 25% predkośći to też nie
byle co, ale zareklamowałeś to neico na wyrost.
Oczywisćie, mogłem coś zwalić (http://pastebin.com/pdbaF76E)




> Drastyczny przyklad dlaczego numeryki nie zawsze obchodza problemy
> kryptografow -- QRNG (quasi-random number generator -- w odroznieniu od
> PRNG/pseudo):
> https://en.wikipedia.org/wiki/Low-discrepancy_sequence
> http://www.johndcook.com/blog/2009/03/16/quasi-random-sequences-in-art-and-integration/

Nie miasząłbym w ogole QRNG i PRNG. To zupełnie inne zagadnienia,
QRNG ma dość ograniczone (choć bardzo potrzebne) zastosowanie.
MT i QMT to nie co tamo, tylko ze względów reklamowych nazywa się
podobnie ;-) Nijak nie obniża wartości zwykłych PRNG.



pzdr
bartekltg