user
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 {\displaystyle r\_{n+1}=a\times r\_{n}+c{\pmod {m}}}}

Where:

* r

  0
  {\displaystyle {\displaystyle r\_{0}}}
   is a seed.
* r

  1
  {\displaystyle {\displaystyle r\_{1}}}
  , 

  r

  2
  {\displaystyle {\displaystyle r\_{2}}}
  , 

  r

  3
  {\displaystyle {\displaystyle r\_{3}}}
  , ..., are the random numbers.
* a
  {\displaystyle {\displaystyle a}}
  , 

  c
  {\displaystyle {\displaystyle c}}
  , 

  m
  {\displaystyle {\displaystyle m}}
   are constants.

If one chooses the values of 

a
{\displaystyle {\displaystyle a}}
, 

c
{\displaystyle {\displaystyle c}}
 and 

m
{\displaystyle {\displaystyle m}}
 with care, then the generator produces a uniform distribution of integers from 

0
{\displaystyle {\displaystyle 0}}
 to 

m
−
1
{\displaystyle {\displaystyle m-1}}
.

LCG numbers have poor quality. 

r

n
{\displaystyle {\displaystyle r\_{n}}}
 and 

r

n
+
1
{\displaystyle {\displaystyle r\_{n+1}}}
 are not independent, as true random numbers would be. Anyone who knows 

r

n
{\displaystyle {\displaystyle r\_{n}}}
 can predict 

r

n
+
1
{\displaystyle {\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 {\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 {\displaystyle state\_{0}}}
. The random sequence is 

r
a
n

d

1
{\displaystyle {\displaystyle rand\_{1}}}
, 

r
a
n

d

2
{\displaystyle {\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 {\displaystyle state\_{n+1}=1103515245\times state\_{n}+12345{\pmod {2^{31}}}}}
* r
  a
  n

  d

  n
  =
  s
  t
  a
  t

  e

  n
  {\displaystyle {\displaystyle rand\_{n}=state\_{n}}}
* r
  a
  n

  d

  n
  {\displaystyle {\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 {\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 {\displaystyle rand\_{n}=state\_{n}\div 2^{16}}}
* r
  a
  n

  d

  n
  {\displaystyle {\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.
assistant
(formerly Perl 6)

We'll define subroutines implementing the LCG algorithm for each version. We'll make them return a lazy list.

```
constant modulus = 2**31;
sub bsd  {
    $^seed, ( 1103515245 * * + 12345 ) % modulus ... *
}
sub ms   {
    map * +> 16, (
	$^seed, ( 214013 * * + 2531011 ) % modulus ... *
    )
}
 
say 'BSD LCG first 10 values (first one is the seed):';
.say for bsd(0)[^10];
 
say "\nMS LCG first 10 values (first one is the seed):";
.say for ms(0)[^10];

```

```
BSD LCG first 10 values (first one is the seed):
0
12345
1406932606
654583775
1449466924
229283573
1109335178
1051550459
1293799192
794471793

MS LCG first 10 values (first one is the seed):
0
38
7719
21238
2437
8855
11797
8365
32285
10450
```