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

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();
}
```

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

In your case , m=7FFFFFFF

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

In your case , m=7FFFFFFF

sorry for lateness in reply..can you please explain

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

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

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.

All Courses

From novice to tech pro — start learning today.