Zainspirowany przez Random ze związanymi rękami :

Cel

Celem tego wyzwania jest napisanie programu, który generuje pseudolosowy strumień bitów, który jest ciągiem 1 i 0, które wydają się być całkowicie losowe, ale w rzeczywistości są generowane w sposób deterministyczny. Twój program powinien wypisać ciąg 1 i 0 (z opcjonalnym białym znakiem) i powinien spełnić następujące wymagania:

1. Biorąc pod uwagę nieograniczony czas i pamięć, twój program musi nadal wyświetlać ciąg 1 i 0 na zawsze
2. Twój program musi wygenerować ponad 1000 losowych bitów w ciągu około jednej minuty na rozsądnej maszynie. Jeśli to wymaganie jest niemożliwe, zmniejszę je.
3. Ciąg bitów może się powtarzać, ale długość powtarzającej się sekcji musi być większa niż 1000 bitów.
4. Ciąg bitów musi przejść jak najwięcej testów losowości (opisanych poniżej), jak to możliwe.
5. Program nie może pobierać żadnych danych wejściowych z zewnętrznych źródeł ani używać wbudowanej funkcji podobnej do rand ().
6. Ze względu na powyższe wymagania program musi wyświetlać ten sam ciąg bitów za każdym razem, gdy jest uruchamiany.

Test losowości nr 1

Ciąg bitów pseudolosowych nie może zawierać żadnego oczywistego wzorca po oględzinach.

Test losowości nr 2 (może ulec zmianie na podstawie komentarzy)

Ciąg bitów musi zawierać równy rozkład 1 i 0. Aby to przetestować (i inne rzeczy), strumień bitów jest podzielony na segmenty o długości 3 bitów, takie jak 101|111|001.

Spośród wszystkich tych segmentów 1/8 z nich powinna mieć trzy jedynki i żadnych zer, 3/8 z nich powinno mieć dwa jedynki, a jeden 0, 3/8 powinno mieć jeden 1 i dwa zera, a 1/8 z nich nie powinny mieć 1 i 3 0.

Test losowości # 3

„Przebieg” jest definiowany jako kolejna seria bitów, z których wszystkie mają tę samą wartość. Ciąg 1001001110ma trzy przebiegi o rozmiarze 1 ( 1..1.....0), dwa przebiegi o rozmiarze 2 ( .00.00....) i jeden przebieg o rozmiarze 3 ( ......111.). Zauważ, że przebiegi nie nakładają się.

Z ciągu 1000 losowych bitów powinno być około 250 serii o rozmiarze 1, 125 serii o rozmiarze 2, 62 serii o rozmiarze 3 itd. Ogólnie rzecz biorąc, dla serii o rozmiarze R powinno być około serii 1000/(2**(R+1))o tej wielkości.

Test losowości # 4

Pierwsze 840 bitów podzielono na dwie połowy po 420 bitów. Każdy bit w pierwszej połowie jest porównywany z odpowiednim bitem w drugiej połowie. Dwa bity powinny pasować przez około pięćdziesiąt procent czasu.

Oto kod źródłowy programu Perl, który wykonuje testy od 2 do 4. Obecnie wymaga, aby ciąg bitów nie zawierał żadnych białych znaków.

Czas Kryterium Zwycięskiego Celu!

Zwycięzcą jest program, który spełnia wszystkie 6 wymagań i wszystkie testy losowości w stopniu, który jest nie do odróżnienia od losowości. Jeśli wiele programów to osiągnie, wygra ten, który zajmuje najwięcej czasu. Jeśli wiele programów to osiągnie, być może będę musiał znaleźć więcej testów losowości, aby działać jak remis.

C, 61

main(s,n){for(n=1u<<31;putchar((s%=n)/(n/2)&1|48);s*=65539);}

Tak, wiem, że to nie jest golf golfowy. Jest to oczywiście raczej rozwiązanie anty -... ale z pewnością spełnia twoje kryteria.

obecnie | głowa -c840
$ ./a.out | głowa -c840 | perl tester.pl
Test 2: 1 (1) 2.93333333333333 (3) 3,1 (3) 0,96666666666666667 (1)
Test 3: 214 99 71 24 7 5 1 1 2 2
Test 4: 0,495238095238095

Długość okresu wynosi 2²⁹.

Mathematica 78 53 znaki

Cyfry binarnej reprezentacji Pi wydają się zachowywać tak, jakby były wytwarzane chaotycznie, chociaż nie jest to udowodnione.

Poniższa prosta procedura deterministycznie zwraca jako ciąg binarne cyfry pi, odpowiadające dcyfrom dziesiętnym:

f[d_]:=ToString@FromDigits@RealDigits[N[Pi,d],2][[1]]

Stosowanie

Jeśli poprosimy o odpowiednik 301 cyfr dziesiętnych Pi, otrzymamy 1000 cyfr binarnych.

f[301]
StringLength[%]

(* out *)
1100100100001111110110101010001000100001011010001100001000110100110001001100011001100010100010111000000011011100000111001101000100101001000000100100111000001000100010100110011111001100011101000000001000001011101111101010011000111011000100111001101100100010010100010100101000001000011110011000111000110100000001001101110111101111100101010001100110110011110011010011101001000011000110110011000000101011000010100110110111110010010111110001010000110111010011111110000100110101011011010110110101010001110000100100010111100100100001011011010101110110011000100101111001111110110001101111010001001100010000101110100110100110001101111110110101101011000010111111111101011100101101101111010000000110101101111110110111101110001110000110101111111011010110101000100110011111101001011010111010011111001001000001000101111100010010110001111111100110010010010010100001100110010100011110110011100100010110110011110111000010000000000111110010111000101000010110001110111111000001011001100011011010010010000011011000011100011

1000 (* characters *)

Ponieważ Pi jest liczbą nieracjonalną, nie ma kropki. Istnieją jednak praktyczne ograniczenia związane z uruchomionym sprzętem.

Test 1 Wygląda mi dobrze.

Test 2

d=301;
Partition[RealDigits[N[Pi,d],2][[1]],{3}];
Tally[%]
(* out *)
{{{1,1,0},35},{{0,1,0},45},{{0,0,0},41},{{1,1,1},40},
{{0,1,1},50},{{1,0,1},32},{{1,0,0},43},{{0,0,1},47}}

Bardziej szczegółowa kontrola:

d=10^6;
Partition[RealDigits[N[Pi,d],2][[1]],{3}];
Tally[%]

{{{1,1,0},138565},{{0,1,0},138146},{{0,0,0},138260},{{1,1,1},138427},
{{0,1,1},139119}, {{1,0,1},138404},{{1,0,0},137926},{{0,0,1},138462}}

Test 3: Działa

d=10^6;
res3=SortBy[Tally@Split@RealDigits[N[Pi,d],2][[1]],Last]/.{a_,b_}:> {Length[a],b}
ListPlot[res3 ,AxesLabel-> {"Run Length","Runs"},AxesOrigin->{0,0}]

Prowadziłem wiele spraw, aby systematycznie sprawdzać rozkład przebiegów. W około 3 milionach cyfr binarnych było 830 tys. Serii 1, 416 tys. Serii 2, 208 tys. Serii 3, 104 tys. Serii 4 itd.

Test 4: Dopasowywanie pierwszej i drugiej połowy danych

Dopasowaniami są 212 przypadków 0 i 2; niedopasowania to 208 przypadków, w których suma odpowiednich cyfr wynosi 1.

d=301;
Tally[Plus@@Partition[Take[RealDigits[N[Pi,d],2][[1]],840],420]]

(* out *)
{{1,208},{0,108},{2,104}}

wyczucie czasu

Obliczenie 3321928 cyfr binarnych zajmuje mniej niż dwie sekundy (co odpowiada 10 ^ 6 cyfr dziesiętnych).

(r=f[10^6]);//AbsoluteTiming
StringLength[r]

(*out*)
{1.785928,Null}    
3321928

Python, 90

g=[19]
print(''.join("01"[(g.append((11*g[-1]+13)%1024)or g[-1])>512]for i in range(1000)))

gjest wartością początkową. Losowe pobieranie próbek wykazuje niezwykle normalny rozkład. Powtarzane losowe pobieranie próbek średnich próbek dało średnią 0.506i standardowe odchylenie .0473(wielkość próbki 1000). Niestety losowość jest bardzo wrażliwa na początkowe nasiona. Ziarno w powyższym kodzie dało mi najlepszą losowość: str

AKTUALIZACJA

Zobaczmy, jak ten kod wytrzymuje testy OP:

Test nr 1

Ten jest nieco subiektywny ... ale dla mnie wygląda dość nieregularnie.

Test nr 2

Trzy 1: 0,141
Dwa 1: 0,371
Jeden 1: 0,353
Zero 1: 0,135

Test nr 3

Działa według rozmiaru:

8: 11
7: 3
6: 7
5: 13
4: 32
3: 67
2: 119
1: 216

Test nr 4

Współczynnik równości: 0,94 To literówka. Wkrótce zaktualizuje prawidłowy numer.

Haskell 74 58

main=print$iterate(read.take 9.show.(^3))7>>=show.(`mod`2)

Dzięki shiona za uproszczenie. Wyniki:

/ pseudorandom | głowa -c 1000

./pseudorandom | głowa -c 1000 | perl test.pl

Test 2: 0,966666666666667 (1) 2,4 (3) 3,3 (3) 1,33333333333333 (1)

Test 3: 260 108 66 33 15 11 5 2

Test 4: 0,495238095238095

Jest to także straszny pseudolosowy generator (podobny do tego, z którego korzystał von-Neuman). Dla tych, którzy nie byli świadomi concatMap == (=<<) == flip . (>>=)(dla list)

Pytanie jest zasadniczo równoważne z „implementacją szyfru strumieniowego”. Wdrażam więc RC4, ponieważ jest to stosunkowo proste.

Nie używam żadnego klucza i upuszczam pierwsze 100000 bitów, ponieważ początek RC4 jest nieco stronniczy, zwłaszcza, że ​​pominąłem harmonogram kluczy. Ale spodziewam się, że przejdzie test nawet bez tego (oszczędzając 20 znaków kodu).

Zwykle wypisuje się pełny bajt na cykl, ale konwersja na binarną jest raczej brzydka w C #, więc po prostu odrzucam wszystko oprócz najmniej znaczącego bitu.

var s=Enumerable.Range(0,256).ToArray();
byte i=0,j=0;
for(int k=0;;k++)
{
    i++;
    j+=(byte)s[i];
    var t=s[i];s[i]=s[j];s[j]=t;
    if(k>99999)
        Console.Write(s[i]+s[j]&1);
}

Lub bez spacji:

var s=Enumerable.Range(0,256).ToArray();byte i=0,j=0;for(int k=0;;k++){i++;j+=(byte)s[i];var t=s[i];s[i]=s[j];s[j]=t;if(k>99999)Console.Write(s[i]+s[j]&1);}

C #, 156 znaków, działa w trybie instrukcji LinqPada. Aby uzyskać pełny program w języku C #, dodaj zwykły szablon.

Możemy również użyć wbudowanych prymitywów kryptograficznych (rozwiązanie Cheater):

var h=SHA256.Create();for(BigInteger i=0;;i++){Console.Write(h.ComputeHash(i.ToByteArray())[0]%2);}

(C #, 99 znaków, działa w trybie instrukcji LinqPada. W przypadku normalnego kompilatora C # musisz dodać trochę kafelka)

Wyjście funkcji kryptograficznych funkcji skrótu zostało zaprojektowane tak, aby było nierozróżnialne od losowych danych, więc spodziewam się, że przejdzie wszystkie testy losowości (trudniejsze, ...) rzucisz na to, ale jestem zbyt leniwy, aby to przetestować.

C, 52 znaki

main(a){for(a=1;putchar(48+a%2);a=a/2^-(a%2)&576);}

To jest 10-bitowy LFSR, wyniki testu:

$ ./a.out |head -c 1000 | perl randtest.pl
Test 2: 1.13333333333333 (1) 2.86666666666667 (3) 3.16666666666667 (3) 0.833333333333333 (1)
Test 3:  251 122 64 32 16 8 4 2  1
Test 4: 0.466666666666667

Sage / Python

Ten program drukuje skrajnie prawe cyfry binarne, które są wspólne dla każdej wystarczająco wysokiej wieży wykładniczej w postaci 3 ^{3 3 3 . .} . Dla wszystkich, jakie kiedykolwiek można było wygenerować, są to najbardziej binarne cyfry liczby Grahama . Sekwencja cyfr jest nieskończona i nie jest okresowa.

m = 1; x = 3; last = 0
while True:
    m *= 2; x = pow(3,x,m); l = len(bin(x))
    print '1' if l > last else '0',
    last = l

W przypadku 1000 cyfr zajęło to mniej niż 2 sekundy; czas będzie jednak zwiększał się znacznie szybciej niż liniowo w liczbie cyfr.

Te wyniki badań z użyciem programu PO za to

Test 2: 1.26666666666667 (1) 3.16666666666667 (3) 2.8 (3) 0.766666666666667 (1)
Test 3:  268 126 61 30 20 7 2  1 1
Test 4: 0.466666666666667

(Zobacz Czy skrajnie prawe cyfry G są losowe ?, aby uzyskać więcej niż 32000 cyfr i dodatkowe testy statystyczne.)

Java, 371 317

Oparty na 128-bitowym LFSR ( dotknięcia bitów pochodzą z noty 52 aplikacji xilinx )

EDYCJA: Nie byłem zadowolony z używania BigInteger, więc ta wersja nie. Zapisałem niektóre postacie. Wynik może być nieco mniej przypadkowy, ponieważ nie mogłem wymyślić dobrej metody „seedowania”.

Nowy kod: Argumenty: BITS_TO_PRINT

class R{public static void main(String[]a){int L=65536;int[]v={0,128,126,101,99};int[]b=new int[L];for(int x=0;x<L;x++)b[x]=(x*x)&1;for(int i=0;i<Integer.parseInt(a[0])+L;i++){if(1!=(b[v[1]]^b[v[2]]^b[v[3]]^b[v[4]]))b[v[0]]=1;else b[v[0]]=0;if(i>L)System.out.print(b[v[0]]);for(int j=0;j<5;j++)v[j]=(v[j]-1)&(L-1);}}}

Stara wersja: Argumenty: SEED, BITS_TO_PRINT

import java.math.BigInteger;class R{public static void main(String[]a){BigInteger v=new BigInteger(a[0]);BigInteger m=new BigInteger("ffffffffffffffffffffffffffffffff",16);for(int i=Integer.parseInt(a[1]);i>0;i--){v=v.shiftLeft(1);if(!(v.testBit(128)^v.testBit(126)^v.testBit(101)^v.testBit(99))){v=v.setBit(0);}v=v.and(m);java.lang.System.out.print(v.testBit(0)?1:0);}}}

Nowa wersja: Przykładowy wynik, bity = 100:

011001100111000110010100100111011100100111000111001111110110001001100000100111111010111001100100011

JavaScript - 1ms do 2ms dla 1000 pseudolosowych bitów (139ms do 153ms dla 100000 bitów)

To rozwiązanie wykorzystuje fakt, że pierwiastki kwadratowe są nieracjonalne, a zatem prawie losowe. Zasadniczo, rozpoczyna się pierwiastek kwadratowy z 2, konwertuje go na binarny, wyrzuca wiodącą część, która pasowała do poprzedniego pierwiastka, dołącza ją do losowego ciągu, powtarza z kolejną wyższą liczbą (lub wraca do 2, jeśli liczba się powtarza i miał co najmniej 30 bitów) i zwraca losowy ciąg, gdy jest wystarczająco długi.

var getDeterministicPseudoRandString = function(length){
    var randString = '';

    var i = 2;
    var prevRand = '';

    outerLoop:
    while(randString.length < length){
        var nextRand, nextFullRand = Math.sqrt(i++).toString(2).substring(1).replace('.', '');
        nextRand = nextFullRand;
        for(var j = prevRand.length; j > 0; j--){
            var replaceString = prevRand.substring(0, j);

            nextRand = nextFullRand;

            if(nextFullRand.indexOf(replaceString) == 0){
                if(j == prevRand.length && j > 30){
                    //start i over at 2
                    console.log('max i reached: ' + i);

                    i = 2;
                    continue outerLoop;
                } else {
                    nextRand = nextFullRand.replace(replaceString, '');
                }

                break;
            }
        }
        prevRand = nextFullRand;

        randString += nextRand;
    }

    return randString.substring(0, length);//Return the substring with the appropriate length
};

Nie przeprowadziłem jeszcze testów, ale wyobrażam sobie, że poradzi sobie z nimi dobrze. Oto skrzypce, dzięki czemu można zobaczyć w akcji. W moich czasach właśnie uruchomiłem program kilka razy i wziąłem najszybsze i najwolniejsze wartości jako zakresy.

Pyton

import hashlib
x=''
while 1:
    h=hashlib.sha512()
    h.update(x)
    x=h.digest()
    print ord(x[0])%2

Powinien mieć okres około 2 ^ 512.

perl, 44 bajty

Wiem, że to nie jest golf golfowy, ale zawsze byłem fanem korzystania z bitów niskiego rzędu prostej funkcji kwadratowej, np .:

$x=1/7;print substr($x*=4-4*$x,9,1)%2while 1

Okres jest dłuższy niż 3 miliardy, ale zabrakło mi miejsca na dysku, aby obliczyć więcej.