The linear congruential generator is a very simple example of a random number generator.

All linear congruential generators use this formula:

 




r

n
+
1


=
a
×

r

n


+
c


(
mod

m
)



{\displaystyle r_{n+1}=a\times r_{n}+c{\pmod {m}}}




Where:

 




r

0




{\displaystyle r_{0}}

 is a seed.
 




r

1




{\displaystyle r_{1}}

, 




r

2




{\displaystyle r_{2}}

, 




r

3




{\displaystyle r_{3}}

, ..., are the random numbers.
 



a


{\displaystyle a}

, 



c


{\displaystyle c}

, 



m


{\displaystyle m}

 are constants.


If one chooses the values of 



a


{\displaystyle a}

, 



c


{\displaystyle c}

 and 



m


{\displaystyle m}

 with care, then the generator produces a uniform distribution of integers from 



0


{\displaystyle 0}

 to 



m
−
1


{\displaystyle m-1}

.

LCG numbers have poor quality. 




r

n




{\displaystyle r_{n}}

 and 




r

n
+
1




{\displaystyle r_{n+1}}

 are not independent, as true random numbers would be. Anyone who knows 




r

n




{\displaystyle r_{n}}

 can predict 




r

n
+
1




{\displaystyle r_{n+1}}

, therefore LCG is not cryptographically secure. The LCG is still good enough for simple tasks like Miller-Rabin primality test, or FreeCell deals. Among the benefits of the LCG, one can easily reproduce a sequence of numbers, from the same 




r

0




{\displaystyle r_{0}}

. One can also reproduce such sequence with a different programming language, because the formula is so simple.

The task is to replicate two historic random number generators. One is the rand() function from BSD libc, and the other is the rand() function from the Microsoft C Runtime (MSCVRT.DLL). Each replica must yield the same sequence of integers as the original generator, when starting from the same seed.

In these formulas, the seed becomes 



s
t
a
t

e

0




{\displaystyle state_{0}}

. The random sequence is 



r
a
n

d

1




{\displaystyle rand_{1}}

, 



r
a
n

d

2




{\displaystyle rand_{2}}

 and so on.



BSD formula

 



s
t
a
t

e

n
+
1


=
1103515245
×
s
t
a
t

e

n


+
12345


(
mod


2

31


)



{\displaystyle state_{n+1}=1103515245\times state_{n}+12345{\pmod {2^{31}}}}


 



r
a
n

d

n


=
s
t
a
t

e

n




{\displaystyle rand_{n}=state_{n}}


 



r
a
n

d

n




{\displaystyle rand_{n}}

 is in range 0 to 2147483647.


Microsoft formula

 



s
t
a
t

e

n
+
1


=
214013
×
s
t
a
t

e

n


+
2531011


(
mod


2

31


)



{\displaystyle state_{n+1}=214013\times state_{n}+2531011{\pmod {2^{31}}}}


 



r
a
n

d

n


=
s
t
a
t

e

n


÷

2

16




{\displaystyle rand_{n}=state_{n}\div 2^{16}}


 



r
a
n

d

n




{\displaystyle rand_{n}}

 is in range 0 to 32767.


The BSD formula was so awful that FreeBSD switched to a different formula.

More info is at Random number generator (included)#C.




 
BEGIN
COMMENT
   Algol 68 Genie checks for integer overflow whereas the reference
   language leaves the result undefined so for portability we need to
   see how wide a variable must be to hold the maximum possible value
   before range reduction. This occurs in the BSD RNG when
   rseed=2147483647 and is therefore 2147483647 * 1103515245 + 12345 =
   2369780942852710860, which itself is 19 decimal digits.  Use
   evironmental queries to determine the width needed.
COMMENT
   MODE RANDINT = UNION (INT, LONG INT, LONG LONG INT);
   RANDINT rseed := (int width > 18 | 0 |:
		     long int width > 18 |
		     LONG 0 | LONG LONG 0);
   PROC srand = (INT x) VOID :
   (rseed | (INT): rseed := x,
    (LONG INT): rseed := LENG x | rseed := LENG LENG x);
   PROC bsd rand = INT :
   BEGIN
      CASE rseed IN
      (INT ri):
      BEGIN
	 INT a = 1103515245, c = 12345, m1 = 2^16, m2 = 2^15;
COMMENT
   That curious declaration is because 2^31 might overflow during
   compilation but the MODE declaration for RANDINT guarantees that it
   will not overflow at run-time.  We assume that an INT is at least
   32 bits wide, otherwise a similar workaround would be needed for
   the declaration of a.
COMMENT
	 INT result = (ri * a + c) MOD (m1 * m2); rseed := result;
	 result
      END,
      (LONG INT rli):
      BEGIN
	 LONG INT a = LONG 1103515245, c = LONG 12345, m = LONG 2^31;
	 LONG INT result = (rli * a + c) MOD m; rseed := result;
	 SHORTEN result
      END,
      (LONG LONG INT rlli) :
      BEGIN
	 LONG LONG INT a = LONG LONG 1103515245,
	 c = LONG LONG 12345, m = LONG LONG 2^31;
	 LONG LONG INT result = (rlli * a + c) MOD  m; rseed := result;
	 SHORTEN SHORTEN result
      END
      ESAC
   END;
   PROC ms rand = INT :
   BEGIN
      CASE rseed IN
      (INT ri):
      BEGIN
	 INT a = 214013, c = 2531011, m1 = 2^15, m2 = 2^16;
	 INT result = (ri * a + c) MOD (m1 * m2); rseed := result;
	 result % m2
      END,
      (LONG INT rli):
      BEGIN
	 LONG INT a = LONG 214013, c = LONG 2531011, m = LONG 2^31, m2 = LONG 2^16;
	 LONG INT result = (rli * a + c) MOD m; rseed := result;
	 SHORTEN (result % m2)
      END,
      (LONG LONG INT rlli) :
      BEGIN
	 LONG LONG INT a = LONG LONG 214013,
	 c = LONG LONG 2531011, m = LONG LONG 2^31, m2 = LONG LONG 2^16;
	 LONG LONG INT result = (rlli * a + c) MOD m; rseed := result;
	 SHORTEN SHORTEN (result % m2)
      END
      ESAC
   END;
   srand (0);
   TO 10 DO printf (($g(0)l$, bsd rand)) OD;
   print (newline);
   srand (0);
   TO 10 DO printf (($g(0)l$, ms rand)) OD;
   srand (0)
END
 