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.




' version 04-11-2016
' compile with: fbc -s console
 
' to seed BSD_lcg(seed > -1)
' to get random number BSD_lcg(-1) or BSD_lcg() or just BSD_lcg
Function BSD_lcg(seed As UInteger = -1) As UInteger
 
    Static As UInteger bsd_state
 
    If seed <> -1 Then
        bsd_state = seed Mod 2 ^ 31
    Else
        bsd_state = (1103515245 * bsd_state + 12345) Mod 2 ^ 31
    End If
 
    Return bsd_state
 
End Function
 
' to seed ms_lcg(seed > -1)
' to get random number ms_lcg(-1) or ms_lcg() or just ms_lcg
Function ms_lcg(seed As Integer = -1) As UInteger
 
    Static As UInteger ms_state
 
    If seed <> -1 Then
        ms_state = seed Mod 2 ^ 31
    Else
        ms_state = (214013 * ms_state + 2531011) Mod 2 ^ 31
    End If
 
    Return ms_state Shr 16
 
End Function
 
' ------=< MAIN >=------
 
Dim As Long i
 
Print "MS generator"
' ms_lcg(0)      ' state = 0 at the start of the program
For i = 1 To 10
    Print Using "###########"; ms_lcg
Next
 
Print
Print "BSD generator"
' BSD_lcg(0)     ' state = 0 at the start of the program
For i  = 1 To 10
    Print Using "###########"; BSD_lcg
Next
 
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End