Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Note that there is more than one common use of the word "linear" in mathematics. $y=ax+b$ is linear in the sense that its graph is a straight line, even though it isn't linear in the sense of linear algebra. –  Gerry Myerson Dec 7 '11 at 11:46
    
Knuth has entire chapter devoted to random numbers, TAOCP, Vol. 2, Chapter 3. In 3.2 he discusses Lehmer's work and the linear congruential method. –  dbasnett Dec 7 '11 at 13:41
1  
@dbasnett Yes, I have read Knuth's work and thats partly the reason why I am asking this question. (Proud owner of the 4 (3 1/2?) volumes) –  Captain Giraffe Dec 7 '11 at 17:43
    
@Gerry Good point. –  Captain Giraffe Dec 7 '11 at 17:44

1 Answer 1

up vote 3 down vote accepted

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.