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 generator   07/03/2017
LINCONG  CSECT
         USING  LINCONG,R12
         LR     R12,R15            set base register
BEGIN    SR     R5,R5              bsdseed=0
         SR     R7,R7              msseed=0
         LA     R8,1               i=1
         L      R9,=F'10'          number of loop
LOOP     M      R4,=F'1103515245'  bsdseed*=1103515245
         A      R5,=F'12345'       bsdseed+=12345
         LR     R3,R5              bsdrand=bsdseed
         LTR    R5,R5              if bsdseed<0
         BP     CONT               then
         L      R3,COMP2             -2**31 
         SR     R3,R5                -bsdseed 
         LPR    R3,R3                bsdrand=abs(-2**31-bsdseed)
CONT     M      R6,=F'214013'      msseed*=214013
         A      R7,=F'2531011'     msseed+=2531011
         XR     R6,R6
         D      R6,TWO16           /2**16
         XDECO  R8,XDEC            i
         MVC    PG(4),XDEC+8
         XDECO  R3,XDEC            bsdrand
         MVC    PG+4(12),XDEC
         XDECO  R7,XDEC            msseed
         MVC    PG+16(7),XDEC+5
         XPRNT  PG,L'PG            print buffer
         LA     R8,1(R8)           i=i+1
         BCT    R9,LOOP            loop
RETURN   XR     R15,R15            set return code
         BR     R14                return to caller
         DS     0F                 alignment
TWO16    DC     XL4'00010000'      2**16
COMP2    DC     XL4'80000000'      -2**31 
PG       DC     CL80' '
XDEC     DS     CL12 
         YREGS  
         END    LINCONG