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.

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.

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 ³² :

$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 ³² ( M = 50971 • 84263 ), a gdy napotkamy wartość, że nie jest ona poprawną 32-bitową liczbą całkowitą (to znaczy większą niż 2 ³² ), 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

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).

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

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();
    }

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;
    }

}

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))

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.

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ę

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));