2
$\begingroup$

How does one interpret the terms "Linear" and "Congruential" as in a "Linear congruential RNG"?

I am used to linearity by $f(ax)=af(x)$. This does not seem to me to hold true in this case ($\bmod$). I have no idea how to interpret the congruential part.

  • 0
    @Gerry Good point.2011-12-07

1 Answers 1

4

Exactly What It Says On The Tin.

Let's break it down by looking at the definition. An LCG is any PRNG that takes the form

$x_{k+1}=(ax_k+b)\bmod M$

where $x_0,a$ and $b$ are some integer parameters, and $M$ is a large integer only slightly below the largest representable integer on the machine.

We can see where the name comes from (which, BTW, is due to D.H. Lehmer): "linear" is due to the fact that the quantity whose remainder we are taking is the result of a linear function ($ax+b$), and "congruential", since we are performing a congruence operation (modulo).