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

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Encryption

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

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