Linear congruential generator
The linear congruential generator is a very simple example of a random number generator. All linear congruential generators use this formula:
Where:
- is a seed.
- , , , ..., are the random numbers.
- , , are constants.
If one chooses the values of , and with care, then the generator produces a uniform distribution of integers from to .
LCG numbers have poor quality. Anyone who knows can predict , therefore LCG is not cryptographically secure. The LCG is still good enough for simple tasks like the Knuth shuffle. Among the benefits of the LCG, one can easily reproduce a sequence of numbers, from the same . 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.
(These formulas should have better wiki formatting.)
BSD formula
Microsoft formula
(Here should be links to the sources of the formulas. Here should explain how the low bits have a short cycle.)
(Here should be some sample numbers for a few seeds, so that one who solves this task can check if one's numbers matches these samples.)
PARI/GP
Note that up to PARI/GP version 2.3.0, random()
used a linear congruential generator.
<lang parigp>BSDseed=Mod(1,1<<31);
MSFTseed=Mod(1,1<<31);
BSD()=BSDseed=1103515245*BSDseed+12345;lift(BSDseed);
MSFT()=MSFTseed=214013*MSFTseed+2531011;lift(MSFTseed)%(1<<31);</lang>