Implement Python programs that can find the cycle length of a linear congruential

random number generator, using Floyd's algorithm.

The terms in the problem statement are likely to be unfamiliar to you, but they are not

difficult to understand and are described in detail below. In the end, this assignment

involves only a few lines of Python code. In order to complete it$,$ you need to be able

to write loops $($for and while$)$ and branch statements $($if$-$else$)$ in Python.

For the purposes of this assignment, a linear congruential random number

generator is defined in terms of four integers: the multiplicative constant a$,$ the

additive constant $b,$ the starting point or seed $c,$ and the modulus m $.$ The purpose of the

generator is to produce a sequence of integers between $0$ and $M-1$ by starting with

$x_0=c$ and iterating:

$x_{n+1}=(a^{**}{x}_n+b)8M$

In Python, the $\%$ operator means modulus or remainder: this keeps the iterates

between $0$ and M$-1.$ For example, the following table shows the sequences that result

for various choices of $a,b,c,$ and M $.$

As with the linear feedback shift register, these sequences are not random, but $($for

proper choices of the parameters$)$ they exhibit many properties of random sequences.

For small values of the parameters, the non$-$randomness is particularly evident:

whenever we generate a value that we have seen before, we enter into a cycle, where

we continually generate the same subsequence over and over again.

In the first two examples above, the cycles are $0-3-6-9-2-5-8-1-4-7-0$ and $1-3-7-5-1,$

of lengths $10$ and $4,$ respectively.

Since there are only M different possibilities, we always must enter such a cycle, but

we want to avoid short cycles.

Your first task is to write a program to print out the sequence for small M$.$ Your

second task is to write a program to compute the cycle length for any M $.$

Part $1$a: print iterates. Write a Python program that reads in four integers $($a$,$ b$,$ c$,$

and M in this order$)$ and prints out the first $M$ values produced by the linear

congruential random number generator for these parameters. Use a for loop and the

following update formula:

$x=(a**x+b)$&$M$

Part $1$b: print iterates nicely. Print the iterates in a nice table with $16$ values per

line and four characters per iterate. Use an if statement with the $\%$ operator to print a

newline character after every $16$ iterations. Use an appropriate print formatting

instruction to get four characters per iterate. Assume that M is $1,000$ or less so that

this is a sufficient amount of space.

Name your program trace. Verify that it behaves as follows:

Perspective. In practice, we often want random integers in a small range, say between

$0$ and $9.$ Typically we do so by using a large M in a linear congruential random

number generator, and then use arithmetic to bring them down into a small range. For

example, the leading digits of the first $50$ terms in the sequence above are:

$0\{\begin{array}{ccc}\text{:}[0,& 8,2,4,3,8,1,1,8,1,& 2]\end{array}$

which is a random$-$looking sequence of integers between $0$ and $9($although the pattern

repeats itself every $50$ iterations$).$ But if we use this method for the last example

above, we get stuck in the cycle

which is not a very random$-$looking sequence. This phenomenon can happen even for

huge M $,$ so we are interested in knowing that our choice of parameters does not lead

to a small cycle.

Floyd's algorithm. The second part of this assignment is to implement a method

known as Floyd's algorithm for finding the cycle length or period. Floyd's algorithm

consists of two phases: $($i$)$ find a point on the cycle, and $($ii$)$ compute the cycle length.

Phase I. To find a point on the cycle, we use the following clever idea: run two

versions of the generator concurrently, one iterating twice as fast as the other,

until both versions have the same value. At some point, both of them are on the

cycle and we have a race on the cycle, with the gap between the faster one and

the slower one shrinking by one on each iteration. Eventually, the faster one

catches up to the slower one, and the two generators are at the same point on

the cycle.

Above is an example of the process with $a=22,b=1,c=0,$ and $M=72.$ In

this example, the cycle is $3-67-35-51-43-11-27-19-59-3,$ and its length is $9.$

Somewhat coincidentally, this happens to be equal to the number of steps until

the fast and slow generators first meet, but this will not be true in general. The

fast generator happens to be at $51$ when the slow one first hits the cycle at $3.$

The fast one is six steps behind the slow one, and catches up$,$ one step at a time.

Phase II$.$ Once we know a value on the cycle, one more trip around th