38 lines
2.2 KiB
Plaintext
38 lines
2.2 KiB
Plaintext
The [[wp:linear congruential generator|linear congruential generator]] is a very simple example of a [[random number generator]].
|
|
|
|
All linear congruential generators use this formula:
|
|
* <math>r_{n + 1} = a \times r_n + c \pmod m</math>
|
|
|
|
|
|
Where:
|
|
* <math>r_0</math> is a seed.
|
|
* <math>r_1</math>, <math>r_2</math>, <math>r_3</math>, ..., are the random numbers.
|
|
* <math>a</math>, <math>c</math>, <math>m</math> are constants.
|
|
|
|
|
|
If one chooses the values of <math>a</math>, <math>c</math> and <math>m</math> with care, then the generator produces a uniform distribution of integers from <math>0</math> to <math>m - 1</math>.
|
|
|
|
LCG numbers have poor quality. <math>r_n</math> and <math>r_{n + 1}</math> are not independent, as true random numbers would be. Anyone who knows <math>r_n</math> can predict <math>r_{n + 1}</math>, therefore LCG is not cryptographically secure. The LCG is still good enough for simple tasks like [[Miller-Rabin primality test]], or [[deal cards for FreeCell|FreeCell deals]]. Among the benefits of the LCG, one can easily reproduce a sequence of numbers, from the same <math>r_0</math>. 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 <code>rand()</code> function from [[:Category:BSD libc|BSD libc]], and the other is the <code>rand()</code> 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 <math>state_0</math>. The random sequence is <math>rand_1</math>, <math>rand_2</math> and so on.
|
|
|
|
|
|
;BSD formula:
|
|
* <math>state_{n + 1} = 1103515245 \times state_n + 12345 \pmod{2^{31}}</math>
|
|
* <math>rand_n = state_n</math>
|
|
* <math>rand_n</math> is in range 0 to 2147483647.
|
|
|
|
|
|
;Microsoft formula:
|
|
* <math>state_{n + 1} = 214013 \times state_n + 2531011 \pmod{2^{31}}</math>
|
|
* <math>rand_n = state_n \div 2^{16}</math>
|
|
* <math>rand_n</math> 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]].
|
|
<br><br>
|