Gibt es ein besseres Problem für PCG.SE als PCG, einen besseren Zufallszahlengenerator, zu implementieren ? Diese neue Veröffentlichung behauptet, einen schnellen, schwer vorhersagbaren, kleinen, statistisch optimalen Zufallszahlengenerator zu präsentieren.

Die minimale C-Implementierung umfasst nur neun Zeilen:

// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    // Advance internal state
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

^{(von: http://www.pcg-random.org/download.html )}

Die Frage ist: Kannst du es besser machen?

Regeln

Schreiben Sie ein Programm oder definieren Sie eine Funktion, die PCG für vorzeichenlose 32-Bit-Ganzzahlen implementiert. Dies ist ziemlich weit gefasst: Sie können eine unendliche Folge ausdrucken, eine pcg32_random_rFunktion und eine entsprechende Struktur definieren usw.

Sie müssen in der Lage sein, Ihren Zufallszahlengenerator entsprechend der folgenden C-Funktion zu setzen:

// pcg32_srandom(initstate, initseq)
// pcg32_srandom_r(rng, initstate, initseq):
//     Seed the rng.  Specified in two parts, state initializer and a
//     sequence selection constant (a.k.a. stream id)

void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq)
{
    rng->state = 0U;
    rng->inc = (initseq << 1u) | 1u;
    pcg32_random_r(rng);
    rng->state += initstate;
    pcg32_random_r(rng);
}

^{(aus: pcg_basic.c:37)}

Das Aufrufen des Zufallsgenerators, ohne ihn vorher zu setzen, ist undefiniertes Verhalten.

Um Ihre Übermittlung einfach zu überprüfen, stellen Sie sicher, dass die Ausgabe bei Verwendung von initstate = 42und wie initseq = 52folgt lautet 2380307335:

$ tail -n 8 pcg.c 
int main()
{
    pcg32_random_t pcg;
    pcg32_srandom_r(&pcg, 42u, 52u);

    printf("%u\n", pcg32_random_r(&pcg));
    return 0;
}
$ gcc pcg.c
$ ./a.out 
2380307335

Wertung

Standardwertung. In Bytes gemessen. Das Niedrigste ist das Beste. Bei Gleichstand gewinnt die frühere Einreichung. Es gelten Standardlücken .

Probelösung

Kompiliert unter gcc -W -Wallsauber (Version 4.8.2).

Vergleichen Sie Ihre Eingabe damit, um sicherzustellen, dass Sie die gleiche Reihenfolge erhalten.

#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    // Advance internal state
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq)
{
    rng->state = 0U;
    rng->inc = (initseq << 1u) | 1u;
    pcg32_random_r(rng);
    rng->state += initstate;
    pcg32_random_r(rng);
}

int main()
{
    size_t i;
    pcg32_random_t pcg;
    pcg32_srandom_r(&pcg, 42u, 52u);

    for (i = 0; i < 16; i++)
    {
        printf("%u\n", pcg32_random_r(&pcg));
    }
    return 0;
}

Sequenz:

2380307335
948027835
187788573
3952545547
2315139320
3279422313
2401519167
2248674523
3148099331
3383824018
2720691756
2668542805
2457340157
3945009091
1614694131
4292140870

CJam, 109 107 104 98 91 Bytes

Dabei werden einige Zeichen außerhalb des ASCII-Bereichs verwendet, jedoch alle innerhalb des erweiterten ASCII-Bereichs. Daher zähle ich jedes Zeichen als Byte (anstatt als UTF-8).

{[2*0:A)|:B{AA"XQô-L-"256b*B1|+GG#%:A;__Im>^27m>_@59m>_@\m>@@~)31&m<|4G#%}:R~@A+:AR];}:S;

Dies ist im Grunde ein genauer Port des C-Codes.

Die Startfunktion ist ein Block, in dem gespeichert ist S, und die Zufallsfunktion ist ein Block, in dem gespeichert ist R. Serwartet initstateund initseqauf den Stapel und sät das PRNG. Rerwartet nichts auf dem Stapel und belässt die nächste Zufallszahl darauf.

Da das Aufrufen Rvor dem Aufrufen Sundefiniertes Verhalten ist, definiere ich es tatsächlich R innerhalb von S . Bis Sie also den Startblock verwenden, Rist es nur eine leere Zeichenfolge und unbrauchbar.

Das stateist in Variable Aund das incist in gespeichert B.

Erläuterung:

"The seed block S:";
[       "Remember start of an array. This is to clear the stack at the end.";
2*      "Multiply initseq by two, which is like a left-shift by one bit.";
0:A     "Store a 0 in A.";
)|:B    "Increment to get 1, bitwise or, store in B.";
{...}:R "Store this block in R. This is the random function.";
~       "Evaluate the block.";
@A+:A   "Pull up initstate, add to A and store in A.";
R       "Evaluate R again.";
];      "Wrap everything since [ in an array and discard it.";

"The random block R:";
AA            "Push two A's, one of them to remember oldstate.";
"XQô-L-"256b* "Push that string and interpret the character codes as base-256 digits.
               Then multiply A by this.";
B1|+          "Take bitwise or of 1 and inc, add to previous result.";
GG#%:A;       "Take modulo 16^16 (== 2^64). Store in A. Pop.";
__            "Make two copies of old state.";
Im>^          "Right-shift by 18, bitwise xor.";
27m>_         "Right-shift by 27. Duplicate.";
@59m>         "Pull up remaining oldstate. Right-shift by 59.";
_@\m>         "Duplicate, pull up xorshifted, swap order, right-shift.";
@@            "Pull up other pair of xorshifted and rot.";
~)            "Bitwise negation, increment. This is is like multiplying by -1.";
31&           "Bitwise and with 31. This is the reason I can actually use a negative value
               in the previous step.";
m<|           "Left-shift, bitwise or.";
4G#%          "Take modulo 4^16 (== 2^32).";

Und hier ist das Äquivalent des Testgeschirrs im OP:

42 52 S
{RN}16*

die genau die gleichen Zahlen druckt.

Teste es hier. Stack Exchange entfernt die beiden nicht druckbaren Zeichen, sodass es nicht funktioniert, wenn Sie das obige Snippet kopieren. Kopieren Sie stattdessen den Code vom Zeichenzähler .

C 195

Ich dachte, jemand sollte eine kompaktere C-Implementierung veröffentlichen, auch wenn es keine Gewinnchance gibt. Die dritte Zeile enthält zwei Funktionen: r()(äquivalent zu pcg32_random_r()) und s()(äquivalent zu pcg32_srandom_r()). Die letzte Zeile ist die main()Funktion, die von der Zeichenanzahl ausgeschlossen ist.

#define U unsigned
#define L long
U r(U L*g){U L o=*g;*g=o*0x5851F42D4C957F2D+(g[1]|1);U x=(o>>18^o)>>27;U t=o>>59;return x>>t|x<<(-t&31);}s(U L*g,U L i,U L q){*g++=0;*g--=q+q+1;r(g);*g+=i;r(g);}
main(){U i=16;U L g[2];s(g,42,52);for(;i;i--)printf("%u\n",r(g));}

Obwohl der Compiler sich beschwert, sollte dies auf einem 64-Bit-Computer ordnungsgemäß funktionieren. Auf einem 32-Bit - Rechnern finden Sie weitere 5 Bytes zu ändern hinzufügen müssen , #define L longum #define L long long( wie in dieser ideone Demo ).

Julia, 218 199 191 Bytes

Das Umbenennen von Datentypen und ein paar andere kleine Tricks haben mir geholfen, die Länge um zusätzliche 19 Bytes zu reduzieren. Hauptsächlich durch Weglassen von zwei :: Int64-Typzuweisungen .

type R{T} s::T;c::T end
R(s,c)=new(s,c);u=uint32
a(t,q)=(r.s=0x0;r.c=2q|1;b(r);r.s+=t;b(r))
b(r)=(o=uint64(r.s);r.s=o*0x5851f42d4c957f2d+r.c;x=u((o>>>18$o)>>>27);p=u(o>>>59);x>>>p|(x<<-p&31))

Erklärung der Namen (mit entsprechenden Namen in der ungolfed Version unten):

# R     : function Rng
# a     : function pcg32srandomr
# b     : function pcg32randomr
# type R: type Rng
# r.s   : rng.state
# r.c   : rng.inc
# o     : oldstate
# x     : xorshifted
# t     : initstate
# q     : initseq
# p     : rot
# r     : rng
# u     : uint32

Initialisieren Sie den Startwert mit Status 42 und Sequenz 52. Aufgrund des kleineren Programms müssen Sie den Datentyp jetzt explizit während der Initialisierung angeben (ca. 14 Byte Code gespeichert). Sie können die explizite Typzuweisung auf 64-Bit-Systemen weglassen:

r=R(42,52) #on 64-bit systems or r=R(42::Int64,52::Int64) on 32 bit systems
a(r.s,r.c)

Produziere den ersten Satz von Zufallszahlen:

b(r)

Ergebnis:

julia> include("pcg32golfed.jl")
Checking sequence...
result round 1: 2380307335
target round 1: 2380307335   pass
result round 2: 948027835
target round 2: 948027835   pass
result round 3: 187788573
target round 3: 187788573   pass
             .
             .
             .

Ich war wirklich überrascht, dass selbst meine ungolfed Julia-Version darunter so viel kleiner ist (543 Bytes) als die Musterlösung in C (958 Bytes).

Ungolfed-Version, 543 Bytes

type Rng{T}
    state::T
    inc::T
end

function Rng(state,inc)
    new(state,inc)
end

function pcg32srandomr(initstate::Int64,initseq::Int64)
    rng.state =uint32(0)
    rng.inc   =(initseq<<1|1)
    pcg32randomr(rng)
    rng.state+=initstate
    pcg32randomr(rng)
end

function pcg32randomr(rng)
    oldstate  =uint64(rng.state)
    rng.state =oldstate*uint64(6364136223846793005)+rng.inc
    xorshifted=uint32(((oldstate>>>18)$oldstate)>>>27)
    rot       =uint32(oldstate>>>59)
    (xorshifted>>>rot) | (xorshifted<<((-rot)&31))
end

Sie initialisieren den Startwert (Anfangszustand = 42, Anfangssequenz = 52) mit:

rng=Rng(42,52)
pcg32srandomr(rng.state,rng.inc)

Dann können Sie Zufallszahlen erstellen mit:

pcg32randomr(rng)

Hier ist das Ergebnis eines Testskripts:

julia> include("pcg32test.jl")
Test PCG
Initialize seed...
Checking sequence...
result round 1: 2380307335
target round 1: 2380307335   pass
result round 2: 948027835
target round 2: 948027835   pass
result round 3: 187788573
target round 3: 187788573   pass
             .
             .
             .
result round 14: 3945009091
target round 14: 3945009091   pass
result round 15: 1614694131
target round 15: 1614694131   pass
result round 16: 4292140870
target round 16: 4292140870   pass

Da ich ein abgründiger Programmierer bin, habe ich fast einen Tag gebraucht, um es zum Laufen zu bringen. Das letzte Mal, dass ich versucht habe, etwas in C (eigentlich C ++) zu programmieren, war fast 18 Jahre her, aber eine Menge Google-Fu hat mir schließlich geholfen, eine funktionierende Julia-Version zu erstellen. Ich muss sagen, ich habe in nur wenigen Tagen auf Codegolf viel gelernt. Jetzt kann ich anfangen, an einer Piet-Version zu arbeiten. Das wird eine Menge Arbeit, aber ich möchte wirklich, wirklich einen (guten) Zufallsgenerator für Piet;)