Que problema melhor para o PCG.SE do que implementar o PCG, um melhor gerador de números aleatórios ? Este novo artigo pretende apresentar um gerador de números aleatórios rápido, difícil de prever, pequeno e estatisticamente ideal.

Sua implementação C mínima é de apenas nove linhas:

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

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

A questão é: você pode fazer melhor?

Regras

Escreva um programa ou defina uma função que implemente o PCG em números inteiros não assinados de 32 bits. Isso é bastante amplo: você pode imprimir uma sequência infinita, definir uma pcg32_random_rfunção e estrutura correspondente, etc.

Você deve poder propagar seu gerador de números aleatórios equivalentemente à seguinte função 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);
}

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

Chamar o gerador de números aleatórios sem propagá-lo primeiro é um comportamento indefinido.

Para verificar facilmente seu envio, verifique se, quando semeado com initstate = 42e initseq = 52, o resultado é 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

Pontuação

Pontuação padrão. Medido em bytes. O mais baixo é o melhor. Em caso de empate, o envio antecipado vence. Aplicam-se brechas padrão .

Solução de amostra

Compila sob gcc -W -Walllimpeza (versão 4.8.2).

Compare seu envio com este para garantir que você obtenha a mesma sequência.

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

Seqüência:

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

CJam, 109 107 104 98 91 bytes

Isso usa alguns caracteres fora do intervalo ASCII, mas todos estão dentro do ASCII estendido, então estou contando cada caractere como um byte (em vez 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;

Esta é basicamente uma porta exata do código C.

A função de semente é um bloco armazenado em S, e a função aleatória é um bloco armazenado em R. Sespera initstatee initseqna pilha e semeia o PRNG. Rnão espera nada na pilha e deixa o próximo número aleatório nela.

Como chamar Rantes de chamar Sé um comportamento indefinido, na verdade eu estou definindo R dentro S , então até você usar o bloco de propagação, Ré apenas uma string vazia e inútil.

O stateé armazenado na variável Ae o incé armazenado em B.

Explicação:

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

E aqui está o equivalente ao equipamento de teste no OP:

42 52 S
{RN}16*

que imprime exatamente os mesmos números.

Teste aqui. O Stack Exchange retira os dois caracteres não imprimíveis, para que não funcione se você copiar o snippet acima. Copie o código do contador de caracteres .

C, 195

Imaginei que alguém deveria postar uma implementação C mais compacta, mesmo que ela não tenha chance de ganhar. A terceira linha contém duas funções: r()(equivalente a pcg32_random_r()) e s()(equivalente a pcg32_srandom_r()). A última linha é a main()função, que é excluída da contagem 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));}

Embora o compilador se queixe, isso deve funcionar corretamente em uma máquina de 64 bits. Em uma máquina de 32 bits você terá que adicionar mais 5 bytes à mudança #define L longpara #define L long long( como neste ideone demonstração ).

Julia, 218 199 191 bytes

Renomear tipos de dados, além de alguns outros truques, me ajudou a reduzir o comprimento em 19 bytes adicionais. Principalmente omitindo duas atribuições do 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))

Explicação dos nomes (com os nomes correspondentes na versão não destruída abaixo):

# 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

Inicialize a semente com o estado 42 e a sequência 52. Devido ao programa menor, é necessário declarar explicitamente o tipo de dados durante a inicialização agora (salvo 14 bytes de código). Você pode omitir a atribuição de tipo explícita em 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)

Produza o primeiro conjunto de números aleatórios:

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

Fiquei realmente surpreso que mesmo minha versão não-Julia de Julia abaixo seja muito menor (543 bytes) do que a solução de amostra em C (958 bytes).

Versão não destruída, 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

Você inicializa a semente (estado inicial = 42, sequência inicial = 52) com:

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

Então você pode criar números aleatórios com:

pcg32randomr(rng)

Aqui está o resultado de um script de teste:

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 sou um programador abismal, levei quase um dia para fazê-lo funcionar. A última vez que tentei codificar algo em C (na verdade, C ++) foi há quase 18 anos, mas muito do google-fu finalmente me ajudou a criar uma versão Julia funcional. Devo dizer que aprendi muito durante apenas alguns dias no codegolf. Agora posso começar a trabalhar em uma versão do Piet. Isso vai dar muito trabalho, mas eu realmente quero um (bom) gerador de números aleatórios para Piet;)