Implement a PCG

Question

What better problem for PCG.SE than to implement PCG, A Better Random Number Generator? This new paper claims to present a fast, hard-to-predict, small, statistically optimal random number generator.

Its minimal C implementation is just about nine lines:

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

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

The question is: can you do better?

Rules

Write a program or define a function that implements PCG on 32-bit unsigned integers. This is fairly broad: you could print out an infinite sequence, define a pcg32_random_r function and corresponding struct, etc.

You must be able to seed your random number generator equivalently to the following C function:

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

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

Calling the random number generator without seeding it first is undefined behaviour.

To easily check your submission, verify that, when seeded with initstate = 42 and initseq = 52, the output is 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

Scoring

Standard scoring. Measured in bytes. Lowest is best. In case of tie, earlier submission wins. Standard loopholes apply.

Sample solution

Compiles under gcc -W -Wall cleanly (version 4.8.2).

Compare your submission to this to make sure you get the same sequence.

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

Sequence:

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

• Knerd: So is your task language related?
• wchargin: @Knerd Nope. The C is just an example.
• Daniel Baird: Can't wait to see a small javascript implementation..

Answer 1

CJam, (削除) 109 (削除ここまで) (削除) 107 (削除ここまで) (削除) 104 (削除ここまで) (削除) 98 (削除ここまで) 91 bytes

This uses some characters outside the ASCII range, but they are all within extended ASCII, so I'm counting each character as a byte (instead of counting as UTF-8).

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

This is basically an exact port of the C code.

The seed function is a block stored in S, and the random function is a block stored in R. S expects initstate and initseq on the stack and seed the PRNG. R doesn't expect anything on the stack and leaves the next random number on it.

Since calling R before calling S is undefined behaviour, I'm actually defining R within S, so until you use the seed block, R is just an empty string and useless.

The state is stored in variable A and the inc is stored in B.

Explanation:

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

And here is the equivalent of the test harness in the OP:

42 52 S
{RN}16*

which prints the exact same numbers.

Test it here. Stack Exchange strips the two unprintable characters, so it won't work if you copy the above snippet. Copy the code from the character counter instead.

• wchargin: Confirmed: works as advertised.

Answer 2

C, 195

I figured someone ought to post a more compact C implementation, even if it stands no chance of winning. The third line contains two functions: r() (equivalent to pcg32_random_r()) and s() (equivalent to pcg32_srandom_r()). The last line is the main() function, which is excluded from the character count.

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

Although the compiler will complain, this should work properly on a 64-bit machine. On a 32-bit machine you'll have to add another 5 bytes to change #define L long to #define L long long (like in this ideone demo).

• wchargin: Confirmed: works as advertised for me (GCC 4.8.2 on Mint 64-bit).
• wchargin: I would have to rule that the srandom function is part of your submission and should be included in the character count. (After all, perhaps you could think of some clever way to optimize this.) This would bring your current score up to 197, by my count.
• r3mainer: @WChargin Ah, OK then. I counted 195 bytes.

Answer 3

Julia, (削除) 218 (削除ここまで) (削除) 199 (削除ここまで) 191 bytes

Renaming data types plus a few other little tricks helped me to cut down the length by additional 19 bytes. Mainly by omitting two ::Int64 type assignments.

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

Explanation of the names (with according names in the ungolfed version below):

# 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

Initialize seed with state 42 and sequence 52. Due to the smaller program you need to state the data type explicitely during initialization now (saved 14 bytes of code or so). You can omit the explicit type assignment on 64-bit systems:

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

Produce first set of random numbers:

b(r)

Result:

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

I was really surprised, that even my ungolfed Julia version below is so much smaller (543 bytes) than the sample solution 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

You initialize the seed (initial state=42, initial sequence=52) with:

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

Then you can create random numbers with:

pcg32randomr(rng)

Here is the result of a test script:

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

As I’m an abysmal programmer, it took me almost a day to get it working. The last time I tried coding something in C (actually C++) was almost 18 years ago, but a lot of google-fu finally helped me to create a working Julia version. I have to say, I have learned a lot during just a few days on codegolf. Now I can start to work on a Piet version. That’s gonna be a whole lot of work, but I really, really want a (good) random number generator for Piet ;)