¿Qué mejor problema para PCG.SE que implementar PCG, un mejor generador de números aleatorios ? Este nuevo artículo pretende presentar un generador de números aleatorios estadísticamente óptimo, rápido, difícil de predecir, pequeño.

Su implementación mínima de C es de aproximadamente nueve líneas:

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

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

La pregunta es: ¿puedes hacerlo mejor?

Reglas

Escriba un programa o defina una función que implemente PCG en enteros sin signo de 32 bits. Esto es bastante amplio: puede imprimir una secuencia infinita, definir una pcg32_random_rfunción y la estructura correspondiente, etc.

Debe poder sembrar su generador de números aleatorios de manera equivalente a la siguiente función 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);
}

^{(a partir de: pcg_basic.c:37)}

Llamar al generador de números aleatorios sin sembrarlo primero es un comportamiento indefinido.

Para verificar fácilmente su envío, verifique que, cuando se siembra con initstate = 42y initseq = 52, el resultado es 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

Tanteo

Puntuación estándar. Medido en bytes. Lo más bajo es lo mejor. En caso de empate, la presentación anterior gana. Se aplican lagunas estándar .

Solución de muestra

Compila bajo gcc -W -Wallcleanly (versión 4.8.2).

Compare su presentación con esto para asegurarse de obtener la misma secuencia.

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

Secuencia:

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

CJAM, 109 107 104 98 91 bytes

Esto usa algunos caracteres fuera del rango ASCII, pero todos están dentro de ASCII extendido, así que cuento cada carácter como un byte (en lugar de contar como UTF-8).

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

Esto es básicamente un puerto exacto del código C.

La función semilla es un bloque almacenado en S, y la función aleatoria es un bloque almacenado en R. Sespera initstatey initseqen la pila y sembrar el PRNG. Rno espera nada en la pila y deja el siguiente número aleatorio en él.

Dado que llamar Rantes de llamar Ses un comportamiento indefinido, en realidad estoy definiendo R dentro S , así que hasta que use el bloque semilla, Res solo una cadena vacía e inútil.

El statese almacena en variable Ay el incse almacena en B.

Explicación:

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

Y aquí está el equivalente del arnés de prueba en el OP:

42 52 S
{RN}16*

que imprime exactamente los mismos números.

Pruébalo aquí. Stack Exchange elimina los dos caracteres no imprimibles, por lo que no funcionará si copia el fragmento anterior. Copie el código del contador de caracteres en su lugar.

C, 195

Supuse que alguien debería publicar una implementación C más compacta, incluso si no hay posibilidad de ganar. La tercera línea contiene dos funciones: r()(equivalente a pcg32_random_r()) y s()(equivalente a pcg32_srandom_r()). La última línea es la main()función, que se excluye del recuento de caracteres.

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

Aunque el compilador se quejará, esto debería funcionar correctamente en una máquina de 64 bits. En una máquina de 32 bits que tendrá que añadir otros 5 bytes al cambio #define L longa #define L long long( al igual que en esta demo Ideone ).

Julia 218 199 191 bytes

Cambiar el nombre de los tipos de datos más algunos otros pequeños trucos me ayudaron a reducir la longitud en 19 bytes adicionales. Principalmente omitiendo dos asignaciones de tipo :: 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))

Explicación de los nombres (con los nombres correspondientes en la siguiente versión sin golf):

# 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

Inicialice la inicialización con el estado 42 y la secuencia 52. Debido al programa más pequeño, debe indicar el tipo de datos explícitamente durante la inicialización ahora (ahorró 14 bytes de código más o menos). Puede omitir la asignación de tipo explícito en sistemas de 64 bits:

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

Produzca el primer conjunto de números aleatorios:

b(r)

Resultado:

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

Realmente me sorprendió que incluso mi versión de Julia, que no aparece en los campos de golf, es mucho más pequeña (543 bytes) que la solución de muestra en C (958 bytes).

Versión sin golf, 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

Inicializa la semilla (estado inicial = 42, secuencia inicial = 52) con:

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

Entonces puedes crear números aleatorios con:

pcg32randomr(rng)

Aquí está el resultado de un script de prueba:

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

Como soy un programador abismal, me llevó casi un día hacerlo funcionar. La última vez que intenté codificar algo en C (en realidad C ++) fue hace casi 18 años, pero una gran cantidad de google-fu finalmente me ayudó a crear una versión funcional de Julia. Tengo que decir que he aprendido mucho durante unos días en codegolf. Ahora puedo comenzar a trabajar en una versión de Piet. Eso va a ser mucho trabajo, pero realmente quiero un generador de números aleatorios (bueno) para Piet;)