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.




 
 [Linear congruential generators for pseudo-random numbers.
  EDSAC program, Initial Orders 2.]
 
 [Library subroutine R9, to read integer constants at load time.
  See Wilkes, Wheeler & Gill, 1951 edition, pages 98 & 148.]
  ..PK
  T 56 K [must be loaded at 56]
  GKT20FVDL8FA40DUDTFI40FA40FS39FG@S2FG23FA5@T5@E4@
 
 [Modification of library subroutine P7.
  Prints non-negative integer, up to 10 digits, right-justified.
  55 locations, load at even address.
  Set up to be called with 'G N', so that caller needn't know its address.
  See Wilkes, Wheeler & Gill, 1951 edition, page 18.]
            T  46 K  [location corresponding to N parameter]
            P  72 F  [load subroutine at 72]
            E  25 K  TN
  GKA3FT42@A47@T31@ADE10@T31@A48@T31@SDTDH44#@NDYFLDT4DS43@TF
  H17@S17@A43@G23@UFS43@T1FV4DAFG50@SFLDUFXFOFFFSFL4FT4DA49@T31@
  A1FA43@G20@XFP1024FP610D@524D!FO46@O26@XFO46@SFL8FT4DE39@
 
 [BSD linear congruential generator.
  Call with 'G B' to initialize, passing seed in 0D.
  Call with 'G 1 B' to get next value, returned in 0D.]
            T  53 K  [location corresponding to B parameter]
            P 140 F  [load subroutine at 140]
            E  25 K  TB GK
      [0]   G  10 @  [jump to initialize]
      [1]   G  15 @  [jump to get next value]
      [2]   PF  PF   [mask, 2^31 - 1]
      [4]   PF  PF   [multiplier]
      [6]   PF  PF   [added constant]
         [Call R9 to set the 3 preceding constants at load time.]
            E69KT2#@
            2147483647F1103515245F12345#
            T8Z
      [8]   PF  PF    [current state]
 
         [Initialize; caller places seed in 0D]
     [10]   A    3 F  [make jump back to caller]
            T   14 @  [plant in code]
            A      D  [load seed passed by caller]
            T    8#@  [store as initial state]
     [14]   Z      F  [overwritten by jump back to caller]
 
         [Get next value from BSD; return it in 0D]
     [15]   A    3 F  [make jump back to caller]
            T   28 @  [plant in code, acc := 0]
            H    4#@  [mult reg := multiplier]
            V    8#@  [acc := state * multiplier]
            LF  LF  L64F  [shift 34 left, done as 13 + 13 + 8]
            A    6#@  [add the constant]
            T      D  [temp store in 0D]
            H    2#@  [mult reg := mask]
            C      D  [acc := result modulo 2^31]
            U    8#@  [update state]
            T      D  [also to 0D for caller]
     [28]   Z      F  [overwritten by jump back to caller]
 
 [Microsoft linear congruential generator.
  Call with 'G M' to initialize, passing seed in 0D.
  Call with 'G 1 M' to get next value, returned in 0D.
  Very similar to code for BSD, so given in condensed form.]
  T47KP180FE25KTMGKG10@G15@PFPFPFPFPFPFE69KT2#@
         2147483647F214013F2531011# [the 3 constants]
  T8ZPFPFA3FT14@ADT8#@ZFA3FT30@H4#@V8#@LFLFL64FA6#@TDH2#@CDU8#@
 [Unlike BSD, MS returns the state divided by 2^16]
            RF  RD  [shift 16 right, done as 15 + 1]
            T    D  [to 0D for caller]
     [30]   Z    F  [overwritten by jump back to caller] 
 
 [Main routine]
            T  220 K  [load at 220]
            G      K  [set theta parameter as usual]
      [0]   PF    PF  [35-bit seed]
         [Use library subroutine R9 to set seed]
            E69K T#@
            1#        [non-negative seed followed by '#']
            T2Z
      [2]   P      F  [negative counter for loop]
      [3]   P   10 F  [to print first 10 values]
         [Characters for printing]
      [4]   B      F
      [5]   D      F
      [6]   E      F
      [7]   M      F
      [8]   S      F
      [9]   C      F  [colon when in figures mode]
     [10]   K 2048 F  [set letters on teleprinter]
     [11]   #      F  [set figures on teleprinter]
     [12]   @      F  [carriage return]
     [13]   &      F  [line feed]
     [14]   K 4096 F  [null]
 
        [Enter with acc = 0]
        [Print 'SEED:' and then the seed]
     [15]   O10@ O8@ O6@ O6@ O5@ O11@ O9@
            A     #@  [load seed]
            T      D  [store in 0D for printing]
     [24]   A   24 @  [pass return address]
            G      N  [call print subroutine]
            O12@ O13@ [print new line]
 
         [Initialize the BSD generator]
            A     #@  [load seed]
            T      D  [pass seed in 0D]
     [30]   A   30 @  [pass return address]
            G      B  [call BSD initializer]
            O10@ O4@ O8@ O5@ O11@ O9@ O12@ O13@  [print 'BSD:']
            S    3 @  [load negative of count]
         [Loop printing values from BSD generator]
     [41]   T    2 @  [update negative counter]
     [42]   A   42 @  [pass return address]
            G    1 B  [call BSD to get next value in 0D]
     [44]   A   44 @  [pass return address]
            G      N  [call print subroutine]
            O12@ O13@ [print new line]
            A    2 @  [load negative counter]
            A    2 F  [increment]
            G   41 @  [loop until counter = 0]
 
 [Microsoft LCG, very similar to BSD, so given in condensed form]
  A#@TDA53@GMO10@O7@O8@O11@O9@O12@O13@S3@T2@A64@G1MA66@GNO12@O13@A2@A2FG63@
 
            O   14 @  [print null to flush teleprinter buffer]
            Z      F  [stop]
            E   15 Z  [define entry point]
            P      F  [acc = 0 on entry]
 