Question

Write an algorithm in pseudocode for generating a sequence of pseudorandom numbers using a linear congruential generator.

Short answer

Procedure congruence generator$(m,c,a,x_0$: integers with $\mathbf{m}\mathbf{\ge }\mathbf{2}\mathbf{,}\mathbf{c}\mathbf{\ge }\mathbf{0}$and $x_0\ge 0)$

$\mathbf{i}\mathbf{=}\mathbf{1}$

while${\mathbf{x}}_{\mathbf{i}}\mathbf{\ne }{\mathbf{x}}_{\mathbf{0}}$

${\mathbf{x}}_{\mathbf{i}\mathbf{+}\mathbf{1}}\mathbf{:=}\mathbf{(}{\mathbf{ax}}_{\mathbf{i}}\mathbf{+}\mathbf{c}\mathbf{)}\mathbf{mod}\mathbf{m}$

$\mathbf{i}\mathbf{-}\mathbf{i}\mathbf{+}\mathbf{1}$

Return${\mathbf{x}}_0,{\mathbf{x}}_1,{\mathbf{x}}_2,{\mathbf{x}}_3,\dots ,{\mathbf{x}}_{\mathrm{i}}$

Step-by-step solution

Step 1

We call the algorithm "congruence generator" and the input is four integers m(at least 2), c (nonnegative), a and ${\mathbf{x}}_0$(nonnegative).

procedure congruence generator: $(m,c,a,x_0$integers with ${\mathbf{m}}^{\mathbf{3}}\mathbf{2}\mathbf{,}{\mathbf{c}}^{\mathbf{3}}\mathbf{0}$and ${{\mathit{x}}_{\mathbf{0}}}^{\mathbf{3}}\mathbf{0}$)

The variable will keep track of the iteration step. Initially we define I as $\mathbf{1}$. We also start by calculating ${\mathit{x}}_{\mathbf{1}}$.

$\mathbf{i}\mathbf{=}\mathbf{1}$

${\mathit{x}}_{\mathbf{1}}\mathbf{:=}\mathbf{(}{\mathbf{a}}_{\mathbf{0}}\mathbf{+}\mathbf{c}\mathbf{)}\mathbf{}\mathbf{modm}$

The algorithm needs to stop if we obtain a term that is equal to the initial termrole="math" localid="1668669191528" $\left(x_i=x_0\right)$. In each iteration step, we need to execute role="math" localid="1668669107112" ${\mathit{x}}_{\mathbf{1}}\mathbf{:=}\mathbf{(}{\mathbf{a}}_{\mathbf{0}}\mathbf{+}\mathbf{c}\mathbf{)}\mathbf{\text{modm}}$

While role="math" localid="1668669248816" ${\mathbf{x}}_{\mathbf{i}}\mathbf{\ne }{\mathbf{x}}_{\mathbf{0}}$

role="math" localid="1668669305263" $\begin{array}{r}{\mathbf{x}}_{\mathbf{i}\mathbf{+}\mathbf{1}}\mathbf{:=}\mathbf{(}\mathbf{a}{\mathbf{x}}_{\mathbf{i}}\mathbf{+}\mathbf{c}\mathbf{)}\mathbf{\text{modm}}\\ \mathbf{i}\mathbf{:=}\mathbf{i}\mathbf{+}\mathbf{1}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\end{array}$

Finally, we return the generate sequence

Return${\mathbf{x}}_0,{\mathbf{x}}_1,{\mathbf{x}}_2,{\mathbf{x}}_3,\dots ,{\mathbf{x}}_i$

Step 2

Combining all these steps, we then obtain the algorithm:

Procedure congruence generator$\mathbf{(}\mathbf{m}\mathbf{,}\mathbf{c}\mathbf{,}\mathbf{a}\mathbf{,}{\mathbf{x}}_{\mathbf{0}}$: integers with$\mathbf{m}\mathbf{\ge }\mathbf{2}\mathbf{,}\mathbf{c}\mathbf{\ge }\mathbf{0}$and

$\mathbf{i}\mathbf{=}\mathbf{1}$

localid="1668669783271" ${\mathit{x}}_{\mathbf{1}}\mathbf{:=}\mathbf{(}{\mathbf{a}}_{\mathbf{0}}\mathbf{+}\mathbf{c}\mathbf{)}\mathbf{}\mathbf{modm}$

While ${\mathbf{x}}_{\mathbf{i}}\mathbf{\ne }{\mathbf{x}}_{\mathbf{0}}$

$\begin{array}{r}{\mathbf{x}}_{\mathbf{i}\mathbf{+}\mathbf{1}}\mathbf{:=}\mathbf{(}{\mathbf{ax}}_{\mathbf{i}}\mathbf{+}\mathbf{c}\mathbf{)}\mathbf{\text{modm}}\\ \mathbf{i}\mathbf{:=}\mathbf{i}\mathbf{+}\mathbf{1}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\end{array}$

Return ${\mathbf{x}}_0,{\mathbf{x}}_1,{\mathbf{x}}_2,{\mathbf{x}}_3,\dots ,{\mathbf{x}}_i$