Activity: Random Number Generation

Modeling Randomness Activities

Author

Manuel D. Rossetti, PhD P.E.

Work in teams. Before each step, write down a prediction; then check it.

The question. A linear congruential generator (LCG) produces a sequence of integers from the recursion

\[R_{i+1} = (a R_i + c) \bmod m,\]

where \(R_0\) is the seed, \(a\) the multiplier, \(c\) the increment, and \(m\) the modulus. The pseudo-random number is \(U_i = R_i/m\). Recall that \(y \bmod m\) is the remainder when \(y\) is divided by \(m\); for example, \(17 \bmod 3 = 2\).

The LCG theorem. An LCG has full period (a period of \(m\)) if and only if all three conditions hold:

  1. The only positive integer that divides both \(m\) and \(c\) is 1.
  2. If \(q\) is a prime number that divides \(m\), then \(q\) divides \(a - 1\).
  3. If 4 divides \(m\), then 4 divides \(a - 1\).

We study the LCG with \(a = 7\), \(c = 3\), \(m = 16\), and seed \(R_0 = 1\).

1. Individually

  1. Compute \(R_1\) and \(U_1\). Check your answer with your team before going on.

2. As a team

  1. Generate five pseudo-random numbers:

    \(i\) \(R_i = (7R_{i-1} + 3) \bmod 16\) \(U_i\)
    1
    2
    3
    4
    5

  2. What do you notice about \(R_5\)? What is the period of this generator?

  3. Use the theorem: does this LCG achieve full period? Check each condition, and justify your answer.

3. Check with code

Setup. Get the starter file LCG.kt from the code/ folder beside this activity. Put it in src/main/kotlin/student/activities in your KSL project, the package the file declares; create the folder if you do not have it. Run its main. It compiles and runs, but prints zeros: the two functions marked TODO are what we write together.

  1. Run with \(a = 7\). Does the program’s table match yours, and its period?

  2. Which multipliers \(a\) between 1 and 15 does the theorem say give full period with \(c = 3\) and \(m = 16\)? Predict, then change a to one of them and run.

  3. The multiplier \(a = 1\) also satisfies the theorem. Write down its sequence. Is it a good generator?

4. Discuss

  1. What are the advantages and the disadvantages of LCGs?

  2. Where are pseudo-random numbers used in everyday life?

If you finish early

Write a loop that prints the period for every multiplier from 1 to 15. Which periods does the theorem predict, and which can it not predict?