GS question - pseudo random number generator

[wayside]

I was aksed this question when having an interview with GS, could not figure out the solution.

Given a generator:
X_{n+1} = ( a * X_{n} + c ) mod m
where Xn is the sequence of pseudorandom values, and
m: 0 < m — the "modulus"
a: 0 < a < m — the "multiplier"
c: 0 <= c < m — the "increment"
X_{0}: 0 < X_{0} < m — the "seed" or "start value"

Now we know the value of X_{0} and X_{50}, find out a, c, and m.

 

[euroazn]

Let's see if a high-school student (me!) can help you :P

Alright, we first let's start off by defining the function explicitly.
Let's just start off with X_{n+1} = ( a * X_{n} + c ) and ignore the modulus.
Now the values are as follows:
X_{0} = X_{0}
X_{1} = aX_{0}+c
X_{2} = a^2X_{0}+ac+c
X_{3} = a^3X_{0}+a^2*c+ac+c
...and so on and so forth. Clearly then,
X_{n} = a^nX_{0}+c([1-a^n]/[1-a]) //Remember sum of a finite geometric series!

To account for the modulus, we just stick mod m at the end. Modular arithmetic is convenient, huh?

So the final explicit formula to the recursive function you have given is:
X_{n} = ( a^nX_{0}+c([1-a^n]/[1-a]) ) mod m

Ok... so what are we given? X_{50} and x_{0} so... we obviously plug those values in!
X_{50} = ( a^50*X_{0}+c([1-a^50]/[1-a]) ) mod m

Now, I'm assuming this is where you got stuck, because frankly this is where I was getting stuck too.

But then I realized that this isn't just some random math problem. This has practical value in computer science. What that means is.... it's likely that m is in the form of 2^n (!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!)

X_{50} = ( a^50*X_{0}+c([a^50-1]/[a-1]) ) mod 2^n

And... now I'm getting stuck here, lol.

Sorry for the mess :}
Somebody pick up from here :P

 

[wayside]

Thanks for the try. Yes, I am stuck at the same place.

 

[roni]

Try googling "linear congruential generator". And, are you sure you are not missing any information ?
Perhaps they didn't want you to reach the final answer, but they just wanted to see your process ?