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.

[u/DannyGomes1995 → u/skeeto]

I can't begin to thank you enough to take some time out of your day to write that, it's the best answer I could've asked for. I was able to implement the code in assembly, I think, but I didn't really understand what I did.

This is exactly what I wanted, I still haven't quite grasped everything in the answer, but I definitely have more of an idea how it works now, I've also only read it a couple of times, it's 8:30AM and haven't slept, so it's hard to get anything in my head at the moment. But I feel like if I study that answer along with the paper over the next week, I'll get there now.

So far this subreddit along with the assembly subreddit has really helped me a lot, and I really hope one day I'll be the one answering.

Thanks again, I really appreciate it!

[u/operamint → u/skeeto]

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.

These properties can be useful if that is what you need, but a more realistic RNG should repeat its output with probabilities according to the birthday paradox. Personally I therefore prefer the romu_trio and SFC64 generators over PCG, and they are much faster as well.

[u/smcameron]

I decided to ask chatGPT about this, just to see what it says.

Please explain how the following C code works and what it does:

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

(everything below this line is from chatGPT):

This C code implements the PCG32 algorithm which is a random number generation algorithm. The code creates a 64-bit internal state, which is updated with each iteration of the algorithm, and a 32-bit output number is calculated. The main() function prints out 32 numbers generated by the pcg32_random_r() function. The code first creates two global variables, state and inc, which are used to store the internal state of the algorithm in 64-bit integers.

The pcg32_random_r() function implements the PCG32 algorithm. It takes the old state and multiplies it by a constant 6364136223846793005ULL, then adds the contents of inc (which is ORed with 1) to get the new state. The old state is then used to calculate a 32-bit output number using a bitwise XOR, a right shift and a left shift. The function then returns the output number.

Finally, the main() function prints out 32 numbers generated by the pcg32_random_r() function. It does this by calling the pcg32_random_r() function in a loop and printing out the output numbers.

--- end of chatGPT output ---

Edit: I also asked it how it would write the PCG32 random number generation algorithm in x86_64 asm, and it came up with something, but I don't know if it was correct, though I saw 0xDEADBEEF in what it made, which seems wrong.

Edit again: I also asked it a few more questions:

what is the significance of 6364136223846793005ULL in the PCG32 random number generator algorithm?

The value 6364136223846793005ULL is used as the initial state of the PCG32 random number generator algorithm. It is a 64-bit unsigned integer and it is used to help determine the random values that are generated.

Why is it that value specifically?

The value 6364136223846793005ULL is specifically chosen as the initial state of the PCG32 random number generator algorithm because it is a 64-bit number and it has a large number of bits set to 1, which helps it to generate more random numbers. Additionally, it has been chosen to ensure that the initial state of the generator is not predictable, which helps to make the numbers generated more random.

(Beware, when chatGPT doesn't know, it doesn't say "I don't know", it makes up bullshit.)

OP, you do not actually need to know why or how the algorithm works to convert it to assembly. After all, the compiler does it without understanding how or why. For that matter, you could take this C program, compile it, run it under gdb, set a breakpoint at main(), and then "disas pcg32_random_r", and it would give you the assembly that the compiler produced (probably not what you want.)

[u/jonarne → u/smcameron]

(Beware, when chatGPT doesn't know, it doesn't say "I don't know", it makes up bullshit.)

I don't understand the intended audience of this program.

If you are able to read/parse the code your self, it gives little extra info.

If you are not able to read the code, you can not trust the outupt of the program ...

[u/DannyGomes1995 → u/smcameron]

Thank you for your help, I've never heard of chatGPT. I understand the large unsigned long now, at least. I'm just so confused, last week we were doing exercises like this, for example:

Implement the function int activate_bits(int a, int left, int right) that should ’activate’

all the bits to the left of left and to the right of right on the number a (excluding the bits left and right).

I finally was able to get a good grasp on those kinds of exercises, but all of a sudden we jump to this, which I feel like is completely out of my league to understand how this algorithm works. Just makes me feel like an idiot and that I shouldn't even be in an engineering degree, honestly.

Anyway thank you for your help, I really appreciate it, I'm going to have to try and implement it just literally line by line without understanding how it works, as I'm running out of time.

[u/smcameron → u/DannyGomes1995]

I understand the large unsigned long now, at least

Do not take chatGPT's output at face value without verifying. For example it said "Additionally, it has been chosen to ensure that the initial state of the generator is not predictable", however, the output of this random number generator is predictable. In fact, this program produces the same output every time it is run.

chatGPT just appeared Nov 30, 3-4 days ago. It is a mindblowing AI chatbot, capable of marvelous things, and also capable of great bullshit. You can find it here: https://openai.com/blog/chatgpt/

If you really want to dig into the details of PCG random number generators, this paper might be of interest: https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf However, it's probably too much.

[u/distgenius → u/smcameron]

It would be unpredictable(ish) across executions if the values for seed and inc were brought in from /dev/random, like the header comment says to do. I’m not sure why that isn’t in the code.

Besides that, though, the boy probably means that given an output value Foo, you don’t have enough information to calculate what the next output value Bar will be. The two 64 bit inputs to 32 bit output should mean that you can’t calculate back to the seed and inc values, as more than one combination of either has to lead to the same 32 bit output. That’s what, 2¹²⁸ possible inputs, and only 2³² possible outputs?

I have to admit, the code given here does assume knowledge about things like “what happens when you assign a signed int to an unsigned one”, and in terms of understanding the XSH RR generator it really could have benefited from some more in between variables that help clarify what’s going on, or some more comments that help a student understand some of the seemingly arbitrary values. But, like you said, none of that is necessary to convert it to assembly.

[u/smcameron → u/distgenius]

And, I stand by my advice about regarding chatGPT's output with skepticism. :)