Erstellen Sie einen Zufallsgenerator, der die Diehard-Tests besteht

50

Obwohl es hier viele Code-Golf-Fragen gibt, bei denen es um Zufälligkeit geht, habe ich noch keine gesehen, bei der es darum geht, einen algorithmischen Pseudozufallszahlengenerator zu erstellen. Es gibt diesen , der Sie bittet, einen Bit-Stream zu generieren, aber die darin enthaltenen Zufallstests waren nicht sehr streng und es ist kein Code-Golf.

Das Programm, das Sie schreiben, verfügt über eine einzelne aufrufbare Funktion, die eine zufällige Ganzzahl von 0 bis 4294967295 zurückgibt. Diese Funktion darf keine Bibliotheken oder andere Funktionen aufrufen, die nicht als Teil des Programms geschrieben wurden, insbesondere Aufrufe von / dev / random oder die eingebaute rand () Bibliothek einer Sprache. Insbesondere sind Sie auf die grundlegenden Operatoren der Sprache beschränkt, in der Sie arbeiten, z. B. Arithmetik, Array-Zugriff und Anweisungen zur bedingten Flusssteuerung.

Die Punktzahl Ihres Programms wird wie folgt berechnet:

Score = C / R

Wobei C die Länge des Codes in Zeichen und R die Anzahl der von Ihrem Generator bestandenen Diehard-Tests ist (Wenn Ihr Zufallsgenerator nicht mindestens einen Diehard-Test besteht, ist seine Punktzahl unendlich und wird disqualifiziert). Ihr Generator besteht einen Diehard-Test, wenn die erzeugte Datei einen Bereich von P-Werten enthält, die gleichmäßig über das Intervall verteilt zu sein scheinen [0, 1).

Verwenden Sie zur Berechnung von R Ihren Zufallszahlengenerator mit seinem Standard-Startwert, um eine 16-MB-Binärdatendatei zu generieren. Jeder Aufruf der Funktion gibt vier Bytes zurück. Wenn Ihre Funktion zu langsam ist, um Bytes zurückzugeben, wird dies einen Kompromiss zum Erreichen einer niedrigen Punktzahl berücksichtigen, indem festgestellt wird, wie schwierig der Test ist. Führen Sie dann die Diehard-Tests durch und überprüfen Sie die angegebenen P-Werte. (Versuchen Sie nicht, diese selbst zu implementieren; verwenden Sie die hier bereitgestellten )

Die niedrigste Punktzahl gewinnt natürlich.

Joe Z.
quelle
Ist Code, für den eine Internetverbindung erforderlich ist, zulässig? (
Ich
Msgstr "Diese Funktion darf keine Bibliotheken oder andere Funktionen aufrufen, die nicht als Teil des Programms geschrieben wurden." Dazu gehören Funktionen für die Internetverbindung. Ihre Generation sollte rein algorithmisch sein.
Joe Z.
Die eingefleischte Suite erwartet Eingabedateien von 10-11 MB.
Primo
Die Verbindung zu den Tests scheint unterbrochen zu sein, hier ist eine mögliche Alternative.
2012rcampion
Wie soll ich das für meine Brain-Flak-Antwort tun (unten entfernt)? Ich denke, der Code ist zu langsam, um praktisch zu sein
Christopher

Antworten:

6

Mathematica, 32/15 = 2,133

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

Eine unkomplizierte Implementierung von BBS .

Binärdatei generiert mit:

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

Zusammenfassung der Ergebnisse:

 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

Voll random.binhier.

Vollständige Protokolldatei hier.

2012rcampion
quelle
28!-67ist etwas unerschwinglich. Gibt es einen kleineren Wert, der in eine 64-Bit-Ganzzahl passt?
Primo
@primo Wie bei Python sind die Ganzzahlen von Mathematica standardmäßig willkürlich genau, sodass dies kein Problem darstellt.
2012rcampion
Ich habe speziell an die Portabilität von C.
primo am
@primo gmplib.org
2012rcampion
21

Perl 28/13 ≈ 2.15

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

Logdatei hier

Perl 29/13 ≈ 2.23

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

Logdatei hier

Dies ist eine Art Variation einer Xorshift-Funktion , bei der anstelle einer Rechtsverschiebung eine Gleitkommadivision verwendet wird. Beide haben 13 von 15 Tests bestanden und nur die Tests 6 und 7 nicht bestanden.

Ich bin mir nicht ganz sicher , wie lange der Zyklus ist, sondern weil der folgende Code in keiner kurzen Zeit nicht beenden, ist es wahrscheinlich die volle 2 32 :

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

Perl 39/10 = 3,9

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

Hinweis: Wenn Sie nach einem Blum-Blum-Shub-ähnlichen PRNG suchen, ist die Lösung von Keith Randall weitaus besser als jede dieser Lösungen .

Wie bei meiner ursprünglichen Lösung unten handelt es sich auch hier um eine Implementierung von Blum Blum Shub, mit einem großen Unterschied. Ich verwende ein Modul, das etwas größer als 2 32 ist ( M = 50971 • 84263 ). Wenn ein Wert gefunden wird, der keine gültige 32-Bit-Ganzzahl ist ( dh größer als 2 32 ), wird der nächste Wert in der zurückgegeben Rotation statt. Im Wesentlichen werden diese Werte herausgeschnitten, so dass der Rest der Rotation ungestört bleibt, was zu einer nahezu gleichmäßigen Verteilung führt.

Es scheint geholfen zu haben. Er besteht nicht nur die gleichen 9 Tests wie zuvor, sondern besteht jetzt auch überzeugend den Mindestabstandstest. Eine Beispielprotokolldatei finden Sie hier .


Perl 33/9 ≈ 3.67 (Ungültig?)

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

Hinweis: Diese Lösung kann als ungültig angesehen werden, da die obersten 0,00037% des Bereichs niemals eingehalten werden.

Eine schnelle und schmutzige Implementierung des Blum Blum Shub . Ich behaupte die folgenden Ergebnisse:

 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

Eine Beispielprotokolldatei finden Sie hier. Sie können die Ergebnisse jederzeit beanstanden. Die Datei für diehard kann auf folgende Weise generiert werden:

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

und dann die Ausgabe in eine Datei umleiten. Der Mindestabstand scheint verstrichen zu sein, aber wenn Sie ihn mehrmals ausführen, liegt er immer nahe bei 1,0 , was auf einen Fehler hinweist.


Einzelheiten

Im Allgemeinen ist der Blum Blum Shub ein schrecklicher PRNG, aber seine Leistung kann durch Auswahl eines guten Moduls verbessert werden. Das von mir gewählte M ist 7027 • 611207 . Beide Primfaktoren, p und q , haben den modularen Rest 3 (mod 4) und gcd (p (p-1), φ (q-1)) = 2 , was so niedrig wie möglich ist.

Obwohl dies die einzigen Kriterien sind, die auf der Wiki-Seite aufgelistet sind, scheint es nicht genug zu sein. Fast das gesamte Modulo, das ich ausprobiert habe, ist bei jedem Test durchgefallen. Aber es gibt eine Handvoll, die einige der Tests bestehen wird, und die, die ich ausgewählt habe, scheint aus irgendeinem Grund außergewöhnlich gut zu sein.

Als letzte Anmerkung scheint Test 5 für sich genommen ein ziemlich guter Indikator dafür zu sein, wie gut der PRNG ist. Wenn es Test 5 nicht fast besteht , wird es den Rest von ihnen spektakulär verfehlen.


BONUS: Perl 62/14 ≈ 4,43

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

Nur für Geekery ist dies eine 32-Bit-Version des PRNG, das im ursprünglichen Tetris für NES verwendet wird. Erstaunlicherweise besteht es 14 der 15 Tests!

 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

Beispielprotokolldatei kann vorher hier stehen .

Zugegeben, das 1..37Bit ist keine exakte Transkription. In der ursprünglichen Version wird die Entropieroutine 60 Mal pro Sekunde aktualisiert und dann in zufälligen Intervallen abgefragt, was weitgehend von Benutzereingaben abhängt. Für alle, die den ROM zerlegen möchten, beginnt die Entropieroutine bei 0xAB47.

Python-artiger Pseudocode:

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
quelle
Ja, ich habe festgestellt, dass Ihr Algorithmus den Bitstream-Test "nicht bestanden" hat, aber tatsächlich einige Werte unter 0,999999 aufweist. Trotzdem scheinen Ihre Tests genau zu sein.
Joe Z.
Es gibt jedoch ein Problem: Zahlen von 4294951589 bis 4294967295 sind unwahrscheinlich (obwohl dies vermutlich ein Grund dafür ist, dass einige der Diehard-Tests fehlgeschlagen sind).
Joe Z.
1
@ JoeZeng ja, das ist ein Problem. Am deutlichsten wird dies in Test 5: Im ersten Durchgang fehlen 151.000 Wörter, in den übrigen fehlen nur 143.000. Eine Lösung wäre, einen Modul zu wählen, der etwas größer als 2 ^ 32 ist, und zu große Werte zuzulassen, um sie auf Null zu setzen, aber ich konnte keinen finden, der gut funktioniert. In diesem Fall aktualisiere ich den Beitrag.
Primo
7

Python, 46/15 = 3,0666

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

Verwendet modulare Exponentiation, um Zufälligkeit zu erzeugen. 2 ** 32-5 ist die größte Primzahl unter 2 ^ 32. (Gleiches gilt, wenn Test 2 nicht ausgeführt werden kann.)

Keith Randall
quelle
Könnten Sie eine Protokolldatei einfügen?
Primo
Hier einloggen
Keith Randall
1
Dummes Windows. Es ging darum, alle Vorkommen von \rund \nnach \r\numzuwandeln, was die Ergebnisse offensichtlich verzerrt. Ein Fix besteht darin, die Datei direkt mit f = open('file.bin', 'wb')und zu schreiben f.write.
Primo
Diese neue Punktzahl unterbietet die vorherige Punktzahl und ist somit die akzeptierte Antwort.
Joe Z.
Diese neue Punktzahl wurde noch einmal unterschritten, daher habe ich die akzeptierte Antwort geändert.
Joe Z.
4

Ruby, 32/15 = 2,1333

Dies ist die in Ruby implementierte Lösung von Keith Randall.

$v=3;def R;$v=$v**3%(2**32-5)end
YenTheFirst
quelle
@JoeZ Dies scheint die neue niedrigste Antwort zu sein, verbunden mit der brandneuen Mathematica-Antwort.
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);}

Dies hat alle Tests bestanden.

Mit nicht zu vielen weiteren Zeichen besteht es TestU01.

Ergebnis: 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.
quelle
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;}

Ergebnisse

Besteht alle mit Ausnahme von Test Nr. 6. Die
Ergebnisse finden Sie unter http://codepad.org/k1NSoyQW

Erläuterung

C # kann einfach nicht mit Ruby und Python um Knappheit konkurrieren, aber ich habe es genossen, es zu versuchen. Es gibt sicherlich andere Werte, die genauso gut funktionieren (dh der Anfangswert für j = 999 und der Divisor = 277). Ich habe diese nach kurzem Experimentieren ausgewählt.

Mit Wrapper zur Dateierstellung

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

}
Richard II
quelle
1

Python 41/15 = 2,73333

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

Irgendwie schummeln mit der eingebauten Hash-Funktion, aber es ist eingebaut, also nicht mehr schummeln als mit anderen eingebauten wie len. Auf der anderen Seite schmerzt es mich, für die global v;Erklärung bezahlen zu müssen ...

Besteht alle Diehard-Tests (Ich hatte ein Problem mit Test Nr. 2 (SEGVs) auf meinem OSX-Rechner. Für meine Punktzahl gehe ich davon aus, dass er bestanden wird).

Hier ist ein Treiber zum Generieren der 16MB-Datei:

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
quelle
Msgstr "Diese Funktion darf keine Bibliotheken oder andere Funktionen aufrufen, die nicht als Teil des Programms geschrieben wurden, insbesondere Aufrufe von / dev / random oder der eingebauten rand () - Bibliothek einer Sprache." Es tut mir leid, aber das disqualifiziert Ihren Eintrag.
Joe Z.
Um klar zu sein, würde "len" auch Ihren Eintrag disqualifizieren.
Joe Z.
Wo ziehst du die Linie? Ist +eine eingebaute Funktion und damit disqualifiziert?
Keith Randall
6
In vielen Sprachen sind Operatoren und Funktionen jedoch identisch. Siehe +und __add__in Python oder Überladen von Operatoren in c ++. Ich weiß, dass ich Haare spalte. Betrachten Sie dieses Beispiel. Kann ich in Python eine Map wie folgt erstellen {'a':5}:? Sie werden wahrscheinlich ja sagen, aber dann denken Sie daran, dass unter der hash('a')Decke gerufen wird, wenn Sie das tun.
Keith Randall
2
Ich nehme an, ich würde die Linie zeichnen, wenn Sie auf diese Weise syntaktisch auf die Funktion verweisen müssen. Wenn Sie in Python einen Hack finden, mit dem Sie direkt auf die Kartenadresse zugreifen können, ohne syntaktisch auf die "Hash" -Funktion zu verweisen, kann ich diesen akzeptieren.
Joe Z.
1

C 38/15 = 2,533

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

Ich konnte die Diehard-Tests auf meinem Computer nicht zum Laufen bringen, aber es besteht die PractRand-Suite für eine Ausgabe von bis zu 8 GB, sodass ich davon ausgehe, dass alle Tests bestanden werden.

user1502040
quelle
0

Brain-Flak , 344 / (ausstehend)

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

Probieren Sie es online!

Dies funktioniert gut, aber die diehard tests Links sind alle kaputt :( also bis wir neue bekommen, habe ich keine endgültige Punktzahl

Dies verwendet das Blum Blum Shub PRNG, so dass es die meisten Fälle bestehen sollte. Die verwendeten Zahlen sind groß genug. In den 16 MB Testfällen werden keine Muster angezeigt

Christopher
quelle
Wenn dies ungültig ist, sag es mir einfach
Christopher
1
Ich zähle 344. Satz: Kein vollwertiges Brain-Flak-Programm hat eine ungerade Anzahl von Bytes.
user202729
0

Ziel-C, 40/1 = 40

Ziemlich cleverer Ansatz, .hashhier etwas auszunutzen , aber ich mag es

for(int v=9;v=@(v).hash;printf("%i",v));
Albert Renshaw
quelle