32
\$\begingroup\$

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
Improve this question
\$\endgroup\$
3
  • \$\begingroup\$ So is your task language related? \$\endgroup\$ Commented Dec 13, 2014 at 21:49
  • \$\begingroup\$ @Knerd Nope. The C is just an example. \$\endgroup\$ Commented Dec 13, 2014 at 21:57
  • 1
    \$\begingroup\$ Can't wait to see a small javascript implementation.. \$\endgroup\$ Commented Jan 28, 2015 at 6:21

3 Answers 3

Reset to default
18
\$\begingroup\$

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 ^27m>_@59m>_@\m>@@~)31&m<|4G#%}:R~@A+:AR];}:S;">the character counter instead.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Confirmed: works as advertised. \$\endgroup\$ Commented Dec 14, 2014 at 2:55
12
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Confirmed: works as advertised for me (GCC 4.8.2 on Mint 64-bit). \$\endgroup\$ Commented Dec 14, 2014 at 23:51
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Dec 14, 2014 at 23:56
  • \$\begingroup\$ @WChargin Ah, OK then. I counted 195 bytes. \$\endgroup\$ Commented Dec 15, 2014 at 0:15
6
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.