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.
źródło
Odpowiedzi:
Mathematica, 32/15 = 2,133
Prosta implementacja BBS .
Plik binarny wygenerowany za pomocą:
Podsumowanie rezultatów:
Pełny
random.bin
tutaj.Pełny plik dziennika tutaj.
źródło
28!-67
jest nieco wygórowany. Czy istnieje mniejsza wartość pasująca do 64-bitowej liczby całkowitej?Perl 28/13 ≈ 2.15
plik dziennika tutaj
Perl 29/13 ≈ 2.23
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 :
Perl 39/10 = 3,9
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?)
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:
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:
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
Tylko dla maniaków jest to 32-bitowa wersja PRNG wykorzystywana w oryginalnym Tetris dla NES. O dziwo, zdaje 14 z 15 testów!
Przykładowy plik dziennika może wcześniej tutaj .
Trzeba przyznać, że
1..37
bit 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ę od0xAB47
.Pseudo-kod w stylu Python:
źródło
Python, 46/15 = 3,0666
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).
źródło
\r
i\n
na\r\n
, co oczywiście wypacza wyniki. Rozwiązaniem jest bezpośrednie zapisanie pliku przy użyciuf = open('file.bin', 'wb')
if.write
.Ruby, 32/15 = 2.1333
To jest rozwiązanie Keitha Randalla, zaimplementowane w Ruby.
źródło
C # 144/15 = 9,6
To przeszło wszystkie testy.
Przy niezbyt dużej liczbie znaków przechodzi TestU01.
Wynik: http://codepad.org/iny6usjV
źródło
C # - 103/14 = 7,36
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
źródło
Python, 41/15 = 2,73333
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ć zaglobal 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:
źródło
+
funkcja jest wbudowana, a zatem zdyskwalifikowana?+
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 przykryciemhash('a')
zostaniesz wezwany.C 38/15 = 2,533
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.
źródło
Brain-Flak , 344 / (w toku)
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ę
źródło
Cel C, 40/1 = 40
Całkiem sprytne podejście, wykorzystujące
.hash
nieco oszukiwać tutaj, ale lubię toźródło