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!