Zbuduj generator liczb losowych, który przejdzie testy Dieharda

50

Chociaż jest tu wiele pytań dotyczących golfa związanych z przypadkowością, nie widziałem jeszcze jednego, który faktycznie wymagałby zbudowania algorytmicznego generatora liczb pseudolosowych. Jest taki, który prosi cię o wygenerowanie strumienia bitów, ale testy losowości podane na tym nie były bardzo rygorystyczne i nie jest to golf kodowy.

Program, który napiszesz, będzie miał pojedynczą wywoływalną funkcję, która zwróci losową liczbę całkowitą od 0 do 4294967295. Ta funkcja nie może wywoływać żadnych bibliotek ani innych funkcji, które nie zostały również zapisane jako część programu, zwłaszcza wywołania do / dev / random lub wbudowaną bibliotekę językową rand (). Mówiąc dokładniej, jesteś ograniczony do podstawowych operatorów języka, w którym pracujesz, takich jak arytmetyka, dostęp do tablicy i instrukcje warunkowej kontroli przepływu.

Wynik twojego programu jest obliczany w następujący sposób:

Score = C / R

Gdzie C jest długością kodu w znakach, a R jest liczbą testów Dieharda, które przeszedł Twój generator (Jeśli generator liczb losowych nie przejdzie co najmniej jednego testu Dieharda, jego wynik to nieskończoność i zostanie zdyskwalifikowany). Twój generator przechodzi test Dieharda, jeśli plik, który generuje, zapewnia zakres wartości P, które wydają się być równomiernie rozmieszczone w przedziale [0, 1).

Aby obliczyć R, użyj generatora liczb losowych z domyślnym ziarnem do wygenerowania pliku danych binarnych o wielkości 16 MB. Każde wywołanie funkcji zwraca cztery bajty; jeśli twoja funkcja jest zbyt wolna, aby zwracać bajty, spowoduje to kompromis w uzyskaniu niskiego wyniku przez to, jak trudno jest przetestować. Następnie przeprowadź go przez testy Dieharda i sprawdź podane wartości P. (Nie próbuj ich wdrażać samodzielnie; skorzystaj z podanych tutaj )

Oczywiście wygrywa najniższy wynik.

Joe Z.
źródło
Czy kod wymagający połączenia z Internetem jest dozwolony? (nie ma dostępu do żadnej losowej funkcji online, ale może ping lub wartości wywołania interfejsu API)
elssar 25.01.2013
„Ta funkcja nie może wywoływać żadnych bibliotek ani innych funkcji, które nie zostały również zapisane w ramach programu”. Obejmuje to funkcje łączności z Internetem. Twoje pokolenie powinno być czysto algorytmiczne.
Joe Z.
Diehard Suite oczekuje plików wejściowych o wielkości 10-11 MB.
primo
Link do testów wydaje się być zepsuty, oto możliwa alternatywa.
2012rcampion
Jak to zrobić w przypadku mojej odpowiedzi na uderzenie mózgu (usunięte poniżej)? Myślę, że kod jest zbyt wolny, aby był praktyczny
Christopher

Odpowiedzi:

6

Mathematica, 32/15 = 2,133

x=3;Mod[x=Mod[x^2,28!-67],2^32]&

Prosta implementacja BBS .

Plik binarny wygenerowany za pomocą:

f = %; (* assigns anonymous function declared in the previous expression to f *)
Export["random.bin", Array[f, 2^22], "UnsignedInteger32"];

Podsumowanie rezultatów:

 1. BIRTHDAY SPACINGS TEST           .684805
 2. OVERLAPPING 5-PERMUTATION TEST   .757608/.455899
 3. BINARY RANK TEST                 .369264/.634256
 4. BINARY RANK TEST                 .838396
 5. THE BITSTREAM TEST                (no summary p-value)    
 6. OPSO, OQSO and DNA                (no summary p-value)
 7. COUNT-THE-1's TEST               .649382/.831761
 8. COUNT-THE-1's TEST                (no summary p-value)
 9. PARKING LOT TEST                 .266079
10. MINIMUM DISTANCE TEST            .493300
11. 3DSPHERES TEST                   .492809
12. SQEEZE                           .701241
13. OVERLAPPING SUMS test            .274531
14. RUNS test                        .074944/.396186/.825835/.742302
15. CRAPS TEST                       .403090/.403088/.277389

Pełny random.bintutaj.

Pełny plik dziennika tutaj.

2012 rcampion
źródło
28!-67jest nieco wygórowany. Czy istnieje mniejsza wartość pasująca do 64-bitowej liczby całkowitej?
primo
@primo Podobnie jak Python, liczby całkowite Mathematica są domyślnie precyzyjnie dowolne, więc nie powoduje to problemów.
2012rcampion
Myślałem specjalnie o przenośności do C.
primo
@primo gmplib.org
2012rcampion
21

Perl 28/13 ≈ 2.15

sub r{$s^=~($s^=$s/7215)<<8}

plik dziennika tutaj

Perl 29/13 ≈ 2.23

sub r{$s^=~($s^=$s<<8)/60757}

plik dziennika tutaj

Są to coś w rodzaju zmiany na Xorshift , z wykorzystaniem podziału zmiennoprzecinkowego zamiast przesunięcia w prawo. Obaj zdają 13 z 15 testów, nie zdają tylko testów 6 i 7.

Nie jestem do końca pewien, jak długi jest ten cykl, ale ponieważ poniższy kod nie kończy się w krótkim okresie czasu, prawdopodobnie jest to pełny 2 32 :

$start = r();
$i++ while $start != r();
print $i;

Perl 39/10 = 3,9

$s=$^T;sub r{~($s=$s*$s%4294969373)||r}

Uwaga: jeśli szukasz PRNG Blum-Blum-Shub-esque, rozwiązanie Keitha Randalla jest znacznie lepsze niż którekolwiek z nich.

Podobnie jak w przypadku mojego oryginalnego rozwiązania poniżej, jest to również implementacja Blum Blum Shub, z jedną zasadniczą różnicą. Korzystam z modułu nieco większego niż 2 32 ( M = 50971 • 84263 ), a gdy napotkamy wartość, że nie jest ona poprawną 32-bitową liczbą całkowitą (to znaczy większą niż 2 32 ), zwraca następną wartość w zamiast tego obrót. W gruncie rzeczy wartości te są przycinane, pozostawiając resztę obrotu niezakłóconą, co powoduje prawie równomierny rozkład.

Wydaje się, że to pomogło. Oprócz pozytywnego wyniku tych samych 9 testów, co teraz, w przekonujący sposób przechodzi również test minimalnej odległości. Przykładowy plik dziennika można znaleźć tutaj .


Perl 33/9 ≈ 3,67 (nieprawidłowy?)

 $s=$^T;sub r{$s=$s*$s%4294951589}

Uwaga: to rozwiązanie może zostać uznane za nieprawidłowe, ponieważ najwyższe 0,00037% zakresu nigdy nie zostanie zaobserwowane.

Szybkie i brudne wdrożenie Blum Blum Shub . Zgłaszam następujące wyniki:

 1. passed - Birthday Spacings
 2. FAILED - Overlapping Permutations
 3. passed - Ranks of 31x31 and 32x32 Matrices
 4. passed - Ranks of 6x8 Matrices
 5. FAILED - Monkey Tests on 20-bit Words
 6. FAILED - Monkey Tests OPSO, OQSO, DNA
 7. FAILED - Count the 1s in a Stream of Bytes
 8. passed - Count the 1s for Specific Bytes
 9. passed - Parking Lot Test
10. FAILED - Minimum Distance Test
11. passed - Random Spheres Test
12. FAILED - The Squeeze Test
13. passed - Overlapping Sums Test
14. passed - Runs Test
15. passed - The Craps Test

Przykładowy plik dziennika można znaleźć tutaj , możesz zakwestionować dowolny z wyników. Plik dla diehard można wygenerować w następujący sposób:

print pack('N', r()) for 1..4194304

a następnie potokowanie danych wyjściowych do pliku. Wygląda na to, że minimalna odległość minęła, ale jeśli uruchomisz ją wiele razy, zawsze będzie bardzo bliska 1,0 , co oznacza awarię.


Detale

Ogólnie rzecz biorąc, Blum Blum Shub jest strasznym PRNG, ale jego wydajność można poprawić, wybierając dobry moduł. M wybrałem to 7027 • 611207 . Oba te czynniki pierwsze, p i q , mają modułową resztę 3 (mod 4) i gcd (φ (p-1), φ (q-1)) = 2 , która jest tak niska, jak to tylko możliwe.

Chociaż są to jedyne kryteria wymienione na stronie wiki, nie wydaje się to wystarczające. Prawie wszystkie moduły, które wypróbowałem, nie zdały każdego testu. Ale jest garstka, która przejdzie niektóre testy, a ten, który wybrałem, wydaje się wyjątkowo dobry, z jakiegokolwiek powodu.

Podsumowując, sam test 5 wydaje się dość dobrym wskaźnikiem tego, jak dobry jest PRNG. Jeśli nie przejdzie prawie testu 5, reszta z nich wypadnie spektakularnie.


BONUS: Perl 62/14 ≈ 4,43

$t=$^T;sub r{$t|=(($s=$s/2|$t%2<<31)^($t/=2))<<31for 1..37;$t}

Tylko dla maniaków jest to 32-bitowa wersja PRNG wykorzystywana w oryginalnym Tetris dla NES. O dziwo, zdaje 14 z 15 testów!

 1. passed - Birthday Spacings
 2. passed - Overlapping Permutations
 3. passed - Ranks of 31x31 and 32x32 Matrices
 4. passed - Ranks for 6x8 Matrices
 5. passed - Monkey Tests on 20-bit Words
 6. passed - Monkey Tests OPSO, OQSO, DNA
 7. FAILED - Count the 1s in a Stream of Bytes
 8. passed - Count the 1s for Specific Bytes
 9. passed - Parking Lot Test
10. passed - Minimum Distance Test
11. passed - Random Spheres Test
12. passed - The Squeeze Test
13. passed - Overlapping Sums Test
14. passed - Runs Test
15. passed - The Craps Test

Przykładowy plik dziennika może wcześniej tutaj .

Trzeba przyznać, że 1..37bit nie jest dokładną transkrypcją. W wersji oryginalnej procedura entropii jest aktualizowana 60 razy na sekundę, a następnie sprawdzana w losowych odstępach czasu, w dużej mierze zależnych od danych wejściowych użytkownika. Dla każdego, kto chce zdemontować pamięć ROM, procedura entropii zaczyna się od 0xAB47.

Pseudo-kod w stylu Python:

carry = entropy_1 & 1
entropy_1 >>= 1
entropy_2 = (entropy_2 >> 1) | (carry << 31)
carry = (entropy_1 & 1) ^ (entropy_2 & 1)
entropy_1 |= carry << 31
primo
źródło
Tak, zauważyłem, że twój algorytm „nie zdał” testu strumienia bitów, ale w rzeczywistości miał kilka wartości poniżej 0,999999. Mimo to twoje testy wydają się dokładne.
Joe Z.
Jest jednak jeden problem, a mianowicie, że liczby od 4294951589 do 4294967295 nie mają szans na wystąpienie (chociaż przypuszczam, że jest to część powodu, dla którego niektóre testy Dieharda zakończyły się niepowodzeniem).
Joe Z.
1
@JoeZeng tak, to jest problem. Jest to najbardziej widoczne w teście 5: w pierwszym uruchomieniu brakuje 151 tys. Brakujących słów, a reszcie brakuje 143 tys. Słów. Jednym rozwiązaniem byłoby wybranie modułu nieco większego niż 2 ^ 32 i dopuszczenie wartości, które są zbyt duże, aby zawinąć je do zera, ale nie byłem w stanie znaleźć takiego, który działa dobrze. Jeśli to zrobię, zaktualizuję wpis.
primo
7

Python, 46/15 = 3,0666

v=3
def R():global v;v=v**3%(2**32-5);return v

Wykorzystuje potęgowanie modułowe do generowania losowości. 2 ** 32-5 to największa liczba pierwsza mniejsza niż 2 ^ 32. (To samo dotyczy braku możliwości uruchomienia testu nr 2).

Keith Randall
źródło
Czy możesz wkleić plik dziennika?
primo
Zaloguj się tutaj: codepad.org/ZWhoGe0t
Keith Randall
1
Głupi Windows. Konwertuje wszystkie wystąpienia \ri \nna \r\n, co oczywiście wypacza wyniki. Rozwiązaniem jest bezpośrednie zapisanie pliku przy użyciu f = open('file.bin', 'wb')i f.write.
primo
Ten nowy wynik podważa poprzedni wynik, więc teraz jest to akceptowana odpowiedź.
Joe Z.
Ten nowy wynik został ponownie podcięty, więc zmieniłem przyjętą odpowiedź.
Joe Z.
4

Ruby, 32/15 = 2.1333

To jest rozwiązanie Keitha Randalla, zaimplementowane w Ruby.

$v=3;def R;$v=$v**3%(2**32-5)end
YenTheFirst
źródło
@JoeZ To wydaje się być nowa najniższa odpowiedź, powiązana z nową odpowiedzią Mathematica.
Riking,
3

C # 144/15 = 9,6

uint a=15,b=26,y;uint q(int n){y=(a*1414549U+876619U)^(b*889453U+344753U);b=a;a=y>>12;return(a%256)<<n;}uint r(){return q(24)|q(16)|q(8)|q(0);}

To przeszło wszystkie testy.

Przy niezbyt dużej liczbie znaków przechodzi TestU01.

Wynik: http://codepad.org/iny6usjV

    uint a = 15;
    uint b = 26;

    byte prng8()
    {
        uint y = ((a * 1414549U + 876619U) ^ (b * 889453U + 344753U)) >> 12;
        b = a;
        a = y;
        return (byte)y;
    }

    uint prng32()
    {
        return ((uint)prng8() << 24) | ((uint)prng8() << 16) | ((uint)prng8() << 8) | (uint)prng8();
    }
Andrew P.
źródło
2

C # - 103/14 = 7,36

double j=999;uint N(){uint i=0,n=0;for(;i++<4;n=n*256+(uint)j%256)for(j/=277;j<100000;j*=j);return n;}

Wyniki

Przechodzi wszystkie oprócz testu nr 6
Zobacz wyniki na http://codepad.org/k1NSoyQW

Wyjaśnienie

C # po prostu nie może konkurować z Ruby i Pythonem o zwięzłość, jak zwykle, ale lubiłem próbować. Z pewnością istnieją również inne wartości, które będą działać równie dobrze (tj. Wartość początkowa dla j = 999 i dzielnik = 277). Wybrałem je po krótkich eksperymentach.

Z opakowaniem do tworzenia plików

class R
{
    public static void Main(string[] args)
    {
        var r = new R();
        using (var f = new System.IO.FileStream(".\\out.bin", System.IO.FileMode.Create, System.IO.FileAccess.Write, System.IO.FileShare.Read))
        using (var b = new System.IO.BinaryWriter(f))
        {
            for (long i = 0; i < 12 * 1024 * 1024; i += 4)
            {

                b.Write(r.N());
            }
        }
    }

    double j = 999;

    uint N()
    {
        uint i = 0, n = 0;
        for (; i++ < 4; n = n * 256 + (uint)j % 256)
            for (j /= 277; j < 100000; j *= j) ;
        return n;
    }

}
Ryszard II
źródło
1

Python, 41/15 = 2,73333

v=0
def R():global v;v=hash(`v`);return v

Trochę oszukuje za pomocą wbudowanej funkcji skrótu, ale jest wbudowana, więc nie więcej oszukiwania niż przy użyciu innych wbudowanych funkcji, takich jak len. Z drugiej strony boli mnie, że muszę zapłacić za global v;wyciąg ...

Przechodzi wszystkie testy Dieharda (miałem problem z testem nr 2, to SEGV na mojej maszynie OSX. Jeśli chodzi o mój wynik, zakładam, że przejdzie).

Oto sterownik do wygenerowania pliku 16 MB:

import sys
for i in xrange(1<<22):
  r=R()
  sys.stdout.write('%c%c%c%c'%(r&255, r>>8&255, r>>16&255, r>>24&255))
Keith Randall
źródło
„Ta funkcja nie może wywoływać żadnych bibliotek ani innych funkcji, które również nie zostały napisane jako część programu, zwłaszcza wywołań do / dev / random lub wbudowanej biblioteki rand () języka”. Przepraszam, ale to dyskwalifikuje twój wpis.
Joe Z.
Dla jasności, „len” również zdyskwalifikuje twój wpis.
Joe Z.
Gdzie rysujesz linię? Czy +funkcja jest wbudowana, a zatem zdyskwalifikowana?
Keith Randall
6
Ale w wielu językach operatory i funkcje są identyczne. Zobacz +iw __add__pythonie lub przeciążenie operatora w c ++. Wiem, że rozszczepiam włosy, więc rozważ ten przykład. W Pythonie mogę stworzyć mapę tak: {'a':5}? Prawdopodobnie powiesz „tak”, ale weź pod uwagę to, że pod przykryciem hash('a')zostaniesz wezwany.
Keith Randall
2
Przypuszczam, że narysowałbym linię, gdy trzeba w ten sposób odwoływać się do funkcji w ten sposób. Jeśli możesz znaleźć włamanie do Pythona, które pozwoli ci na bezpośredni dostęp do adresu mapy bez składniowego odwoływania się do funkcji „hash”, mogę to zaakceptować.
Joe Z.
1

C 38/15 = 2,533

long long x;f(){return(x+=x*x+9)>>32;}

Nie mogłem uruchomić testów Dieharda na moim komputerze, ale przeszedł on pakiet PractRand dla maksymalnie 8 GB mocy wyjściowej, więc zakładam, że przeszedłby je wszystkie.

użytkownik1502040
źródło
0

Brain-Flak , 344 / (w toku)

<>((()()){})<> push the amount of iterations to do for the PRNG
(((((((((((((((((((((((((((((((((((()()()){}()){})){}{}){()()()()({}[()])}{})){}{})){}{})()){}{})()){}{})){}{})){}{}){}())){}{})){}{})()){}{})()){}{})){}{})){}{})()){}{})()){}{}) push M (one of the values for the Blum Blum Shub PRNG
((((((((((((()()()){}){}){})){}{}){()({}[()])}{}){}())){}{})()){}{}) push s see above
<>{({}[()])<>starts the loop
(({({})({}[()])}{}) squares the current number
(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]({}))mods by M
<>}{}<>loop ends

Wypróbuj online!

Działa to dobrze, ale wszystkie linki do testów twardych są zepsute :( więc dopóki nie otrzymamy nowych, nie mam końcowego wyniku

To używa Blum Blum Shub PRNG, więc powinno przejść większość przypadków. Użyte liczby są wystarczająco duże, a 16 MB przypadków testowych nie pojawi się

Krzysztof
źródło
jeśli to nieważne, po prostu powiedz mi
Christopher
1
Liczę 344. Twierdzenie: Żaden program w pełni golfowy Flak mózgu nie ma nieparzystej liczby bajtów.
user202729,
0

Cel C, 40/1 = 40

Całkiem sprytne podejście, wykorzystujące .hashnieco oszukiwać tutaj, ale lubię to

for(int v=9;v=@(v).hash;printf("%i",v));
Albert Renshaw
źródło