Are mixed LCG and combined LCG same thing?

  • Topic: Comp Sci 
  • Thread starter shivajikobardan
  • Start date
  • Tags Tags
    Mixed
2 replies · 3K views · last reply
shivajikobardan
Messages
637
Reaction score
54
Homework Statement
Linear Congruential Generators
Relevant Equations
Congruence equation
The whole problem arouse because there's no authentic local source. One thing that I need to learn is are these both same thing? Or are different? Is combined LCG also LCG or anything can be called combined method? Even our teachers aren't very sure of it(as they were not the ones who designed this curriculum or know the internal details of the course etc)

Is there any difference between "mixed Linear congruential generator" and "combined linear congruential generator". Are they same thing or different thing?

It's pretty confusing. No 2 books have explained about both topics. No books I've read yet, have talked about both of these.It's getting more confusing as I read more texts about it.
Slide titled Linear-Congruential Generators (Cont): Lehmer's choices a = 23 and m = 10^8+1, generalization x_n = ax_{n-1} + b mod m, and note that mixed means both multiplication by a and addition of b.

It says "mixed LCG" or "LCG" are the same thing.
https://www.cse.wustl.edu/~jain/iucee/ftp/k_26rng.pdf
Slide titled Combined Generators: adding random numbers from two or more generators, w_n = (x_n + y_n) mod m, with L'Ecuyer (1986) example recurrences x_n = 40014 x_{n-1} mod 2147483563 and y_n = 40692 y_{n-1} mod 2147483399.

Slide titled Combined Generators (Cont), showing two linear congruential recurrences w_n = 157w_{n-1} mod 32363 and x_n = 146x_{n-1} mod 31727, a third y_n = 142y_{n-1} mod 31657, and v_n = (w_n - x_n + y_n) mod 32362.

Text from a slide: When c not equal to 0, the form is called the mixed congruential method; when c = 0, it is known as the multiplicative congruential method. The words mixed and multiplicative are highlighted in orange.

https://www.eg.bucknell.edu/~xmeng/Course/CS6337/Note/master/node40.html

Excerpt from a textbook page: "roulette wheel labeled from zero to m. The terms of multiplicative and mixed congruential methods are used to denote linear congruential sequences with c = 0 and c ≠ 0, respectively. Dividing Xn by m, real random numbers are obtained", with "c = 0 and c ≠ 0" highlighted in green.

Optical Communication with Chaotic Lasers: Applications of Nonlinear Dynamics and Synchronization
Textbook page titled Combining Generators, with text on summing outputs of several linear congruential generators and equations 2.9 and 2.10 for L'Ecuyer's combination.

Monte Carlo Methods in Financial Engineering

Textbook page excerpt, section 7.3.2 'Combined Linear Congruential Generators', with the words generator, Linear, Congruential and combined highlighted in yellow; body text discusses random-number generators with period 2^31 - 1 and simulation of complex systems, page 227 of Random-Number Generation.

Printed textbook page on combined multiplicative congruential generators, with equations for W_i and X_i combining k generators, the R_i output formula, and the maximum period p = (m_1 - 1)(m_2 - 1)...(m_k - 1)/2^(k-1).

Jerry Banks
Printed textbook excerpt titled Combination Generators, describing combining random number generators by defining z_i = x_i ⊙ y_i, where ⊙ is exclusive-or or addition modulo M, and the cycle length can reach the product of the periods.

Molecular Modeling and Simulation: An Interdisciplinary Guide
By Tamar Schlick
Printed textbook page under heading 2.1 Linear Congruential Generators, giving the recurrence x_n = (sum from i=1 to k of a_i x_{n-i} + c) mod m as equation (1), with u_n = x_n / m as equation (1a), and the mixed LCG with k = 1.

This tells LCG and Mixed LCG is same thing in usage.

PROBABILITY AND STATISTICS - Volume II: Probabilistic Models and Methods ...
edited by Reinhard Viertl

Typeset equations defining a linear congruential generator: x_i = a x_{i-1} MOD m, u_i = x_i / m, x_0 in {1,...,m-1}, i > 0, with text above saying LCGs are sensitive to parameters and that c>0 gives mixed LCGs and c=0 is the other case.

Encyclopedia of Information Science and Technology, Fifth Edition
edited by Khosrow-Pour D.B.A., Mehdi

Printed textbook page, section 2.2.5.3 Mixed congruential methods, with the words mixed, method and generator highlighted in yellow. Text describes using two distinct generators together to improve random number quality.


Textbook page section 2.2.5.2 Congruential method: text defines X_n = (c × X_{n-1} + a_0) MOD N_max (2.86) and X_n = (16807 × X_{n-1}) MOD (2^31 − 1) (2.87) for the 32-bit linear congruential algorithm (CONG).

A Guide to Monte Carlo Simulations in Statistical Physics
By David Landau, Kurt Binder

Handwritten notes: (3) When c ≠ 0 and a > 1, then the generator is said to be mixed congruential generator, i.e. X_{i+1} = (aX_i + c) mod m, i = 0,1,2,... followed by an example with X0 = 27, R0 = 0.27, a = 17, b = 43, m = 100.

Local source
Text from lecture notes defining combined linear congruential generators: the combined output X_i equals the sum of (-1)^(j-1) times X_{i,j} mod m_1 - 1, with R_i defined piecewise and maximum period p = (m_1-1)(m_2-1)...(m_k-1)/2^(k-1).

Local source
Text excerpt titled Combined Linear Congruential Method: defines the combined generator as X(i) = sum from j=1 to k of [(-1)^(j-1) * X(i,j)] mod m(j) - 1, and gives R(i) = X(i)/m(j) if X(i) > 0, else (m(j) - 1)/m(j) if X(i) = 0.

local source

After reading these sources, it feels they're different but my local sources are confusing me. It feels LCGs are specifically just multiplicative and mixed. Whereas, combined Genrators doesn't necessarily named LCG.
 
I am not going to read all of that, but I think all your questions are qickly answered by Wikipedia: https://en.wikipedia.org/wiki/Linear_congruential_generator

In short
  • A linear congruential generator (LCG) has the form ## x_{n+1} = (a x_n +c) \bmod m ##.
  • A mixed congruential generator is an LCG with ## c \ne 0 ## (edit: presumably because it has a 'mix' of a multiplicative and constant term).
  • A multiplicative congruential generator (aka Lehmer RNG) is an LCC with ## c = 0 ## (edit because it only has a multiplicative term).
  • A "Combined Linear Congruential Generator" is simply a combination of two or more LCGs: one example is the Wichmann Hill generator I see mentioned in one of your references; again wikipedia has more on these: https://en.wikipedia.org/wiki/Combined_linear_congruential_generator
I don't think this is the first time it has turned out that 10 minutes on Wikipedia would have been the best use of your time.
 
  • Like
Likes   Reactions: Delta2 and shivajikobardan
Thanks, I'll use wikipedia for confusions like this from now.