Problem 24

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

Seed one PRNG with another

Due: February 1
Points: 4

Frank wants to generate random numbers in the range 0 up to 6.

He decides to use a linear recurrence to generate pseudo-random numbers with parameters m=7 and k=4. He uses multiplier values

\[a_1=0,\quad a_2=6,\quad, a_3=4,\quad, a_4=2\]

to achieve the maximal period since \(x^4 - 6x^2 - 4x - 2\) is a primitive polynomial mod 7 (according to Wolfram alpha).

Frank needs the four initial values of the array, \(X_{-3}, X_{-2}, X_{-1}, X_0\), to seed this PRNG. But Frank is lazy and only wants to get the first of these values, \(X_{-3}\), from a "true" random process. The other 3 seed values will be obtained by a different PRNG, a Lehmer LCG with seed value \(X_{-3}\).

For the Lehmer LCG, Frank uses m=7 of course and a=3, since 3 is a primitive root mod 7, also according to Wolfram Alpha.

Part 1 (1 point). Starting with \(X_{-3}=4\), use the Lehmer LCG to determine the four seed values \(X_{-3}\) through \(X_0\).

Part 2 (2 points). Using these seed values, tell me the first 10 integers output from the linear recurrence specified above.

Part 3 (1 point). Do you think Frank's method of generating random numbers is good? Why or why not? Be specific!