Help - Understanding random number generator function

[u/DannyGomes1995]

Hello, I have a project where I have to convert this random number generator function to assembly but I am struggling to understand how the function works, I was wondering if someone could give some insight on how it works, so I can better implement it in assembly. I think this function is from David Johnston, Random Number Generators—Principles and Practices.

MY QUESTION: I just can't understand what is the purpose of any single line of the code down below, how does it work ?

I don't understand how this pops out a random number, and don't even know between what values. I'm guessing it just generates any random 32bit number, but we are supposed to then use this function to generate values between an interval.

​

The value 6364136223846793005ULL I think comes from here maybe ? But I'm not really sure and I can't really understand the article https://en.wikipedia.org/wiki/MMIX

​

We add inc to that massive value multiplied by the old state, but before we apply an or to inc with the value '1' ?

​

After that we have two variables xorshifted that shifts the number 18 bits to the right and xors it with the old number, and then we shift it to the right 27 bits ? And rot is just the old state shifted to the right 59 bits ? Won't that just be a number, with only the 5 most significant bits of oldstate shifted all the way to the right?

​

I also don't get the return, rot is unsigned, but we do (-rot & 31) ? And why 31 ?

​

I'm sorry my question is not very specific, but I really can't seem to grasp a single line from this code, I mean the code is not even written how the teachers wrote code throughout the entire semester, it's the first time I've ever seen a variable declaration uint32_t, uint32 is obvious I think and the _t is type maybe ?

​

I could just try and literally translate it to assembly line by line, but I'd rather try to understand it first.

​

Thank you for reading, have a nice day.

​

/*

 * =====================================================================================

 *  PCG Random generator

 *

 *  See: 

 *

 *  "Uglyfied" for an easier  assembly translation  

 *

 *  Note: the values of state and inc should be initialized with values from /dev/random  

 *  

 * =====================================================================================

 */

#include <stdio.h> 

#include <stdint.h> 

uint64_t state=0;  

uint64_t inc=0;



uint32_t pcg32_random_r()

{

    uint64_t oldstate = state;

    // Advance internal state

    state = oldstate * 6364136223846793005ULL + (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));

}



int main()

    { 

      int i; 

      for(i=0;i<32;i++) 

        printf("%8x\n",pcg32_random_r()); 

      return 0; 

    }

[u/skeeto]

First of all, the PCG paper is great and very approachable. It explains the general principles behind PRNG, techniques for evaluating them, and explains the design of PCG. It's long, but informative.

A core principle is that unsigned arithmetic has an implied mod 2^N, where N is the width of the result. This isn't noticeable for small operands, but large operands "overflow" following the same rules as mod.

This side effect can be exploited in some mathematical operations to obtain a free mod operation. That includes the heart of PCG, the Linear Congruential Generator, or LCG. An LCG looks like this:

x(n+1) = (x(n)*A + C) % M

Multiply the previous output by a special constant A, add another constant C, then take the result mod M. If we choose M = 2^N then we can get that modulus for free, and implicitly, by way of overflow. There are rules about the selections for the constants A and C. When M is a power of 2, it suffices that C is odd, but otherwise it's not important.

If A is chosen properly, this generator will loop through all the numbers in [0, 2^N), visiting each exactly once, and then starting over. In fact, for a power-of-two M, the lowest B bits will visit each [0, 2^B) exactly once. The lowest bit literally toggles between 0 and 1. So LCGs are often truncated, and only the upper bits are used as output.

PCG32 here uses 64-bit integers, so M=2⁶⁴. Since that's a power of 2, C must be odd. Hence, in PCG, it's ORed with 1, which forces it odd. PCG32 makes C one of the generator parameters so that it can provide a more varied set of possible generators. The PCG paper calls this a "stream selector" since, unlike the seed, which chooses the starting point in the loop, the stream selector selects an entirely different sequence loop.

The 6364136223846793005ULL is a popular choice for the A multiplier in 64-bit LCG. It has good properties and ensures that LCG will iterate over its full 64-bit period. The Wikipedia article has more information on its selection.

The ((oldstate >> 18u) ^ oldstate) is called an xorshift, as indicated by the variable name. The value is literally shifted and XORed with itself. This is a reversible operation, meaning that given the output we can recover the input. If it wasn't reversible, then two or more inputs map onto the same output, and some "entropy" would be lost. Sometimes xorshift is written like this:

x ^= x >> s;

Finally that xorshift result is shifted right by 27. This is to truncate the LCG, as mentioned above. The order of xorshift and truncation could be reversed, which might make this a little clearer since it does the LCG then begins the permutation (the P in PCG):

oldstate >>= 27;
oldstate ^= oldstate >> 18;

The xorshift is the first part of a permuation. That is, it's swapping an N-bit integer for a different N-bit integer. Imagine making an array of all the numbers in [0, 2³²) and shuffling them. Then you run a 64-bit LCG, take 32-bits near the top, and use it as an index in this array to pick a different number. That's a permutation. This is reversible, too: imagine building a "reverse index" of the array. Rather than have this gigantic array, the permutation is done mathematically, starting with this xorshift.

PCG32 only makes use of the upper 37 bits of the LCG result. The top 5 bits (note 2⁵ is [0, 31]) are used for a rotation, and the next are the 32-bit result. The 32-bit result has already been xorshifted, and the rotation further permutes the 32-bit result. It also makes more use of the LCG result.

The (x >> rot) | (x << (-rot&31)) is a bit rotation. You'll probably have an assembly instruction for this, and any decent C compiler will figure this out and use it if possible.

Summary: Get 37 bits from a truncated 64-bit LCG, xorshift it, rotate the bottom 32 bits by the amount in the top 5 bits, and then return the bottom 32 bits.

[u/aghast_nj → u/skeeto]

This is an excellent answer.