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

Open in new window

oggiemcAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

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

shajithchandranCommented:

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
0
shajithchandranCommented:
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


In your case , m=7FFFFFFF
0
oggiemcAuthor Commented:
hi shajithchandran,

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
0
shajithchandranCommented:
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
shajithchandranCommented:
isn't the question answered ?
0

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
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Encryption

From novice to tech pro — start learning today.