This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 32

Seed one PRNG with another

Due: February 9
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!