Czy jest lepszy problem dla PCG.SE niż wdrożenie PCG, lepszego generatora liczb losowych ? Ten nowy artykuł twierdzi, że przedstawia szybki, trudny do przewidzenia, mały, statystycznie optymalny generator liczb losowych.

Jego minimalna implementacja C wynosi około dziewięciu linii:

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

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

Pytanie brzmi: czy możesz zrobić lepiej?

Zasady

Napisz program lub zdefiniuj funkcję, która implementuje PCG na 32-bitowych liczbach całkowitych bez znaku. Jest to dość szerokie: możesz wydrukować nieskończoną sekwencję, zdefiniować pcg32_random_rfunkcję i odpowiednią strukturę itp.

Musisz być w stanie zainicjować generator liczb losowych w sposób równoważny z następującą funkcją C:

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

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

Wywołanie generatora liczb losowych bez inicjowania go jest niezdefiniowanym zachowaniem.

Aby łatwo sprawdzić przesłanie, sprawdź, czy po wysianiu za pomocą initstate = 42i initseq = 52dane wyjściowe są następujące 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

Punktacja

Standardowa punktacja. Mierzone w bajtach. Najniższa jest najlepsza. W przypadku remisu wcześniejsze zgłoszenie wygrywa. Obowiązują standardowe luki .

Przykładowe rozwiązanie

Kompiluje się w trybie gcc -W -Wallczysto (wersja 4.8.2).

Porównaj swoje zgłoszenie z tym, aby upewnić się, że otrzymujesz tę samą sekwencję.

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

Sekwencja:

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

CJam, 109 107 104 98 91 bajtów

Wykorzystuje to niektóre znaki spoza zakresu ASCII, ale wszystkie znajdują się w rozszerzonym ASCII, więc liczę każdy znak jako bajt (zamiast liczenia jako UTF-8).

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

Jest to w zasadzie dokładny port kodu C.

Funkcja inicjująca jest blokiem przechowywanym w S, a funkcja losowa jest blokiem przechowywanym w R. Soczekuje initstatei initseqna stosie i rozstawienie PRNG. Rnie oczekuje niczego na stosie i pozostawia na nim kolejną losową liczbę.

Ponieważ wywołanie Rprzed wywołaniem Sjest nieokreślonym zachowaniem, tak naprawdę definiuję R wewnątrz S , więc dopóki nie użyjesz bloku początkowego, Rjest to tylko pusty ciąg i bezużyteczny.

stateJest przechowywany w zmiennej Ai incjest przechowywany w B.

Wyjaśnienie:

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

A oto odpowiednik uprzęży testowej w OP:

42 52 S
{RN}16*

która drukuje dokładnie te same liczby.

Sprawdź to tutaj. Wymiana stosu usuwa dwa niedrukowalne znaki, więc nie będzie działać, jeśli skopiujesz powyższy fragment kodu. Zamiast tego skopiuj kod z licznika znaków .

C, 195

Uznałem, że ktoś powinien opublikować bardziej zwartą implementację C, nawet jeśli nie ma szans na wygraną. Trzeci wiersz zawiera dwie funkcje: r()(równoważne z pcg32_random_r()) i s()(równoważne z pcg32_srandom_r()). Ostatni wiersz jest main()funkcją, która jest wykluczona z liczby znaków.

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

Chociaż kompilator będzie narzekał, powinien działać poprawnie na komputerze 64-bitowym. Na komputerze 32-bitowym trzeba będzie dodać kolejne 5 bajtów do zmian #define L longna #define L long long( jak w tym demo ideone ).

Julia, 218 199 191 bajtów

Zmiana nazw typów danych oraz kilka innych małych sztuczek pomogło mi zmniejszyć długość o dodatkowe 19 bajtów. Głównie poprzez pominięcie dwóch przypisań typu :: Int64 .

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

Objaśnienie nazw (z odpowiednimi nazwami w wersji bez golfa poniżej):

# 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

Zainicjuj seed ze stanem 42 i sekwencją 52. Ze względu na mniejszy program musisz teraz wyraźnie podać typ danych podczas inicjalizacji (zapisano około 14 bajtów kodu). Możesz pominąć jawne przypisanie typu w systemach 64-bitowych:

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

Utwórz pierwszy zestaw liczb losowych:

b(r)

Wynik:

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

Byłem naprawdę zaskoczony, że nawet moja niepoddana golfowi wersja Julii poniżej jest o wiele mniejsza (543 bajty) niż przykładowe rozwiązanie w C (958 bajtów).

Wersja bez golfa, 543 bajty

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

Inicjujesz ziarno (stan początkowy = 42, sekwencja początkowa = 52) za pomocą:

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

Następnie możesz tworzyć losowe liczby za pomocą:

pcg32randomr(rng)

Oto wynik skryptu testowego:

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

Ponieważ jestem programistą bezmyślnym, uruchomienie go zajęło mi prawie dzień. Ostatni raz próbowałem napisać coś w C (właściwie C ++) prawie 18 lat temu, ale wiele google-fu pomogło mi w końcu stworzyć działającą wersję Julii. Muszę powiedzieć, że wiele się nauczyłem podczas zaledwie kilku dni na codegolf. Teraz mogę zacząć pracować nad wersją Piet. To będzie dużo pracy, ale naprawdę bardzo chcę (dobrego) generatora liczb losowych dla Piet;)