# linear congruential generator

Hi everyone,

Ive been asked to do an assignment to test the randomness of a linear congruential generator..We've been given the code implemented in c..the problem is i dont really see how this code relates to the theoretical LCG equation i.e X[n+1] = (aX[n] + c) mod m..So i would be very appreciative if someone could explain the rand32() function in this code and how it implements the theoretical equation above..

many thanks
oggie
``````#include<stdio.h>
#include<stdint.h>

uint16_t rand16();
uint32_t rand32();

uint16_t n, userChosenValue = 0; //Change this for different seed values.
uint16_t numberOfValues = 10; //Change this depending on your needs.
uint32_t seed;
uint32_t mlcg,p,q;
uint64_t tmpseed;

int main(){

/* Calculate and print a series of 16 bit random numbers */
seed = (uint32_t)(userChosenValue + 1);

printf("16 Bit:\n\n");
for (n=0;n<numberOfValues;n++){
printf("%.4x\n",rand16());
}

/* Calculate and print a series of 32 bit random numbers */
seed = (uint32_t)(userChosenValue + 1);

printf("\n\n32 Bit:\n\n");
for (n=0;n<numberOfValues;n++){
printf("%.8x\t\t\n",rand32());
}

return 0;
}

/* Return the next 32 bit random number */
uint32_t rand32() {

tmpseed =  (uint64_t)33614U * (uint64_t)seed;
q = tmpseed; 	/* low */
q = q >> 1;
p = tmpseed >> 32 ;		/* hi */
mlcg = p + q;
if (mlcg & 0x80000000) {
mlcg = mlcg & 0x7FFFFFFF;
mlcg++;
}
seed = mlcg;

return mlcg;
}

/* Return low 16 bits of next 32 bit random number */
uint16_t rand16() {
return (uint16_t)rand32();
}
``````
###### Who is Participating?

Commented:
0

Commented:

The below statement is
aX[n] + c
q = q >> 1;  <==== This is a part of aX[n]
p = tmpseed >> 32 ;           /* hi */
mlcg = p + q;

And mod operator can be done like this.
x%y =  if(x>y) {
z=x&(y-1);
z=z+1;
}

Above one is true only if y is 2^n-1

0

Commented:
opps.. i didnt paste the first three lines.. here is the complete things

X[n+1] = (aX[n] + c) mod m

X[n] is the last random value.

aX[n] is = tmpseed =  (uint64_t)33614U * (uint64_t)seed; /seed is the last value (X[n])

The below statement is  aX[n] + c

q = q >> 1;  <==== This is a part of aX[n]
p = tmpseed >> 32 ;           /* hi */
mlcg = p + q;

And mod operator can be done like this.
x%y =  if(x>y) {
z=x&(y-1);
z=z+1;
}

Above one is true only if y is 2^n-1

0

Author Commented:
hi shajithchandran,

q = q >> 1;  <==== This is a part of aX[n]
p = tmpseed >> 32 ;           /* hi */
mlcg = p + q;

basically why are there 1 and 32 bit shifts being done here and how is it related to (aX[n] + c) mod m??

plus another question i have is, why do we use hexadecimal numbers for these types of algorithms?? is it quicker for computers to compute hexadecimal than decimal??

many thanks
oggiemc
0

Commented:
Refer http://en.wikipedia.org/wiki/Linear_congruential_generator.

Basically, all these values are researched values.
If you look at Apple CarbonLib in the above link. you can see 'a' is 16807. But in your case its 33614 which is double of 16807. So they multiply with 33614 and divide by two (by shifting left by one). Both of these look same, but actually the results can vary if the multiplicated output overflows.

Everything is ultimately represented in binary.... so its not going to make it quicker by using hexadecimal number. If you see that table, the value for m is 2^31 -1 = this is nothing by 0x7FFFFFFF. Its easy to write and remember rather than using the decimal equivalent (2147483647).
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.