Inspiriert von Random mit gebundenen Händen :

Das Ziel

Ziel dieser Herausforderung ist es, ein Programm zu schreiben, das einen pseudozufälligen Bitstrom generiert. Dabei handelt es sich um eine Folge von Einsen und Nullen, die rein zufällig zu sein scheint, aber tatsächlich deterministisch generiert wird. Ihr Programm sollte eine Zeichenfolge von 1 und 0 (mit optionalem Leerzeichen) ausgeben und die folgenden Anforderungen erfüllen:

1. Angesichts der unbegrenzten Zeit und des unbegrenzten Speichers muss Ihr Programm für immer eine Zeichenfolge von 1 und 0 ausgeben
2. Ihr Programm muss auf einem vernünftigen Computer in etwa einer Minute mehr als 1000 zufällige Bits ausgeben. Wenn diese Anforderung nicht möglich ist, werde ich sie verringern.
3. Die Bitfolge kann sich wiederholen, die Länge des Wiederholungsabschnitts muss jedoch mehr als 1000 Bit betragen.
4. Die Bitfolge muss so viele Zufallstests wie möglich bestehen (siehe unten).
5. Das Programm darf keine Eingaben von externen Quellen entgegennehmen oder eine integrierte rand () - ähnliche Funktion verwenden.
6. Aufgrund der obigen Anforderung muss das Programm bei jeder Ausführung genau dieselbe Bitfolge ausgeben.

Zufallstest # 1

Die Folge von Pseudozufallsbits darf bei der Sichtprüfung kein offensichtliches Muster enthalten.

Zufallstest # 2 (Änderungen aufgrund von Kommentaren vorbehalten)

Die Bitfolge muss eine Gleichverteilung von 1 und 0 enthalten. Um dies (und auch andere Dinge) zu testen, wird der Bitstrom in Segmente unterteilt, die 3 Bits lang sind, wie z 101|111|001.

Von all diesen Segmenten sollten 1/8 drei Einsen und keine Nullen haben, 3/8 sollten zwei Einsen und eine 0 haben, 3/8 sollten eine 1 und zwei Nullen haben und 1/8 von ihnen sollten keine Einsen und drei Nullen haben.

Zufallstest # 3

Ein "Durchlauf" ist definiert als eine aufeinanderfolgende Reihe von Bits, die alle den gleichen Wert haben. Die Saite 1001001110hat drei Läufe der Größe 1 ( 1..1.....0), zwei Läufe der Größe 2 ( .00.00....) und einen Lauf der Größe 3 ( ......111.). Beachten Sie, dass Läufe nicht überlappen.

Aus einer Folge von 1000 zufälligen Bits sollten ungefähr 250 Läufe der Größe 1, 125 Läufe der Größe 2, 62 Läufe der Größe 3 usw. bestehen. Im Allgemeinen sollten für Laufgröße R ungefähr 1000/(2**(R+1))Läufe dieser Größe vorhanden sein.

Zufallstest # 4

Die ersten 840 Bits sind in zwei Hälften von jeweils 420 Bits aufgeteilt. Jedes Bit in der ersten Hälfte wird mit dem entsprechenden Bit in der zweiten Hälfte verglichen. Die beiden Bits sollten in etwa fünfzig Prozent der Fälle übereinstimmen.

Hier ist der Quellcode eines Perl-Programms, das die Tests 2 bis 4 ausführt. Ab sofort muss die Bitfolge kein Leerzeichen enthalten.

Zeit für das Zielgewinnkriterium!

Der Gewinner ist das Programm, das alle 6 Anforderungen und alle Zufälligkeitstests in einem von der Zufälligkeit nicht unterscheidbaren Maße besteht. Wenn dies mit mehreren Programmen erreicht wird, gewinnt das Programm, dessen Wiederholung am längsten dauert. Wenn dies mit mehreren Programmen erreicht wird, muss ich möglicherweise mehr Zufallstests finden, um als "Tie-Breaker" zu fungieren.

C 61

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

Ja, ich weiß, dass es kein Code-Golf ist. Dies ist offensichtlich eher ein Anti-Lösungsansatz ... aber es erfüllt sicher genug Ihre Kriterien.

raus | Kopf -c840
$ ./a.out | kopf -c840 | perl tester.pl
Test 2: 1 (1) 2.93333333333333 (3) 3.1 (3) 0.9666666666667 (1)
Test 3: 214 99 71 24 7 5 1 1 2 2
Test 4: 0.495238095238095

Die Periodenlänge beträgt 2²⁹.

Mathematica 78 53 Zeichen

Die Ziffern der binären Darstellung von Pi scheinen sich so zu verhalten, als ob sie chaotisch erzeugt würden, obwohl dies nicht bewiesen ist.

Die folgende einfache Routine gibt die Binärziffern von pi, die dDezimalziffern entsprechen, deterministisch als Zeichenfolge zurück :

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

Verwendung

Wenn wir das Gegenstück von 301 Dezimalstellen von Pi anfordern, erhalten wir 1000 Binärstellen.

f[301]
StringLength[%]

(* out *)
1100100100001111110110101010001000100001011010001100001000110100110001001100011001100010100010111000000011011100000111001101000100101001000000100100111000001000100010100110011111001100011101000000001000001011101111101010011000111011000100111001101100100010010100010100101000001000011110011000111000110100000001001101110111101111100101010001100110110011110011010011101001000011000110110011000000101011000010100110110111110010010111110001010000110111010011111110000100110101011011010110110101010001110000100100010111100100100001011011010101110110011000100101111001111110110001101111010001001100010000101110100110100110001101111110110101101011000010111111111101011100101101101111010000000110101101111110110111101110001110000110101111111011010110101000100110011111101001011010111010011111001001000001000101111100010010110001111111100110010010010010100001100110010100011110110011100100010110110011110111000010000000000111110010111000101000010110001110111111000001011001100011011010010010000011011000011100011

1000 (* characters *)

Da Pi eine irrationale Zahl ist, gibt es keine Periode. Es gibt jedoch praktische Einschränkungen aufgrund der verwendeten Hardware.

Test 1 Sieht für mich gut aus.

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

Genauere Prüfung:

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: Läuft

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

Ich habe eine große Anzahl von Fällen durchlaufen, um die Verteilung der Läufe systematisch zu überprüfen. In ungefähr 3 Millionen Binärziffern gab es 830.000 Läufe mit 1, 416.000 Läufen mit 2, 208.000 Läufen mit 3, 104.000 Läufen mit 4 usw.

Test 4: Übereinstimmung der ersten und zweiten Hälfte der Daten

Die Übereinstimmungen sind die 212 Fälle von 0 und 2; Die Nichtübereinstimmungen sind die 208 Fälle, in denen die Summe der entsprechenden Ziffern 1 ist.

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

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

Zeitliche Koordinierung

Die Berechnung von 3321928 Binärziffern (entsprechend 10 ^ 6 Dezimalziffern) dauert weniger als zwei Sekunden.

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

gist der Startwert. Die Zufallsauswahl zeigt eine bemerkenswert normale Verteilung. Wiederholte Zufallsauswahl der Probenmittel ergab einen Mittelwert von 0.506und eine Standardabweichung von .0473(Probengröße von 1000). Unglücklicherweise ist die Zufälligkeit sehr empfindlich gegenüber anfänglichem Saatgut. Der Samen im obigen Code gab mir die beste Zufälligkeit: p

AKTUALISIEREN

Mal sehen, wie dieser Code den Tests des OP standhält:

Test # 1

Das ist ein bisschen subjektiv ... aber es sieht für mich ziemlich unregelmäßig aus.

Test # 2

Drei Einsen: 0,141
Zwei Einsen : 0,371
Eins Eins: 0,353 Nullen
: 0,135

Test Nr. 3

Läuft nach Größe:

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

Test Nr. 4

Gleichheitsverhältnis: 0,94 Dies ist ein Tippfehler. Wird bald mit der richtigen Nummer aktualisiert.

Haskell 74 58

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

Danke an Shiona für die Vereinfachung. Ergebnisse:

/ pseudozufällig | Kopf -c 1000

./pseudozufall | Kopf -c 1000 | perl test.pl

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

Test 3: 260 108 66 33 15 11 5 2

Test 4: 0,495238095238095

Dies ist auch ein schrecklicher Pseudo-Zufallsgenerator (ähnlich dem von von-Neuman verwendeten). Für diejenigen, die es nicht wussten concatMap == (=<<) == flip . (>>=)(für Listen)

Die Frage ist im Wesentlichen gleichbedeutend mit "Implementieren einer Stream-Verschlüsselung". Also implementiere ich RC4, da es relativ einfach ist.

Ich verwende keinen Schlüssel und lasse die ersten 100000 Bits fallen, da der Beginn von RC4 ein bisschen verzerrt ist, insbesondere, weil ich den Schlüsselzeitplan übersprungen habe. Aber ich würde erwarten, dass es Ihren Test auch ohne das besteht (20 Zeichen Code sparen).

Normalerweise würde man ein volles Byte pro Zyklus ausgeben, aber in C # ist die Konvertierung in eine Binärdatei ziemlich hässlich, so dass ich einfach alles außer dem niedrigstwertigen Bit verwerfe.

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

Oder ohne Leerzeichen:

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 Zeichen, funktioniert im Anweisungsmodus von LinqPad. Für ein vollständiges C # -Programm fügen Sie die übliche Kesselplatte hinzu.

Wir könnten auch eingebaute Krypto-Primitive verwenden (Cheater-Lösung):

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

(C #, 99 Zeichen, funktioniert im Anweisungsmodus von LinqPad. Für den normalen C # -Compiler müssen Sie ein wenig Boilerplate hinzufügen.)

Die Ausgabe von kryptografischen Hash-Funktionen ist so konzipiert, dass sie nicht von zufälligen Daten unterschieden werden kann. Daher erwarte ich, dass alle Zufallstests (die härter sind, ...) bestanden werden, aber ich bin zu faul zum Testen.

C 52 Zeichen

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

Dies ist ein 10-Bit-LFSR, Testergebnisse:

$ ./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

Salbei / Python

Dieses Programm gibt die am weitesten rechts stehenden Binärziffern aus, die jedem ausreichend hohen Exponentiationsturm der Form 3 ^{3 3 3 gemeinsam sind . .} . Für alles, was jemals möglich war, sind dies die am weitesten rechts stehenden Binärziffern von Grahams Zahl . Die Ziffernfolge ist unendlich und nicht periodisch.

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

Bei 1000 Stellen dauerte dies weniger als 2 Sekunden. Die Zeit nimmt jedoch viel schneller als linear in der Anzahl der Stellen zu.

Die Testergebnisse mit dem OP-Programm sind

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

(Weitere Informationen zu mehr als 32000 Stellen und zusätzlichen statistischen Tests finden Sie unter Sind die am weitesten rechts stehenden Stellen von G zufällig ? .)

Java, 371 317

Basiert auf einem 128-Bit- LFSR (Bit-Taps stammen aus der XILINX-App, Anmerkung 52 )

EDIT: Ich war nicht zufrieden mit der Verwendung von BigInteger, daher funktioniert diese Version nicht. Einige Charaktere gespeichert. Die Ausgabe könnte etwas weniger zufällig sein, da ich mir keine gute Methode für das "Säen" vorstellen könnte.

Neuer Code: Argumente: 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);}}}

Alte Version: Argumente: 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);}}}

Neue Version: Beispielausgabe, Bits = 100:

011001100111000110010100100111011100100111000111001111110110001001100000100111111010111001100100011

JavaScript - 1 ms bis 2 ms für 1000 pseudozufällige Bits (139 ms bis 153 ms für 100000 Bits)

Diese Lösung nutzt die Tatsache, dass Quadratwurzeln irrational und damit ziemlich zufällig sind. Grundsätzlich benötigt man die Quadratwurzel von 2, konvertiert sie in eine Binärzahl, wirft den führenden Teil aus, der mit der vorherigen Wurzel übereinstimmt, hängt ihn an die zufällige Zeichenfolge an und wiederholt ihn mit der nächsthöheren Zahl (oder zurück zu 2, wenn die Zahl wiederholt wird) und war mindestens 30 Bit lang) und gibt die zufällige Zeichenfolge zurück, sobald sie lang genug ist.

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

Ich habe die Tests noch nicht durchgearbeitet, aber ich kann mir vorstellen, dass sie gut funktionieren werden. Hier ist eine Geige, damit Sie es in Aktion sehen können. Für meine Zeit habe ich das Programm nur mehrmals ausgeführt und die schnellsten und langsamsten Werte als Bereiche verwendet.

Python

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

Sollte eine Periode von ungefähr 2 ^ 512 haben.

Perl, 44 Bytes

Ich weiß, dass dies kein Codegolf ist, aber ich war schon immer ein Fan von Bits niedriger Ordnung einer einfachen quadratischen Funktion, zB:

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

Der Zeitraum ist länger als 3 Milliarden, aber mir ist der Speicherplatz ausgegangen, um mehr zu berechnen.