C++: Linear Congruential Generator

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 \times r_n + c \pmod m$

Where:

$r 0$ is a seed.
$r 1$ , $r 2$ , $r 3$ , …, are the random numbers.
$a$ , $c$ , $m$ are constants.

If one chooses the values of $a$ , $c$ and $m$ with care, then the generator produces a uniform distribution of integers from $0$ to $m - 1$ .

LCG numbers have poor quality. $r n$ and $r n + 1$ are not independent, as true random numbers would be. Anyone who knows $r n$ can predict $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$ . 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$ . The random sequence is $r a n d 1$ , $r a n d 2$ and so on.

BSD formula:

$state_{n + 1} = 1103515245 \times state_n + 12345 \pmod{2^{31}}$
$r a n d n = s t a t e n$
$r a n d n$ is in range 0 to 2147483647.

Microsoft formula:

$state_{n + 1} = 214013 \times state_n + 2531011 \pmod{2^{31}}$
$rand_n = state_n \div 2^{16}$
$r a n d n$ is in range 0 to 32767.

#include <iostream>
 
//--------------------------------------------------------------------------------------------------
using namespace std;
 
//--------------------------------------------------------------------------------------------------
class mRND
{
public:
    void seed( unsigned int s ) { _seed = s; }
 
protected:
    mRND() : _seed( 0 ), _a( 0 ), _c( 0 ), _m( 2147483648 ) {}
    int rnd() { return( _seed = ( _a * _seed + _c ) % _m ); }
 
    int _a, _c;
    unsigned int _m, _seed;
};
//--------------------------------------------------------------------------------------------------
class MS_RND : public mRND
{
public:
    MS_RND()  { _a = 214013; _c = 2531011; }
    int rnd() { return mRND::rnd() >> 16; }
};
//--------------------------------------------------------------------------------------------------
class BSD_RND : public mRND
{
public:
    BSD_RND() { _a = 1103515245; _c = 12345; }
    int rnd() { return mRND::rnd(); }
};
//--------------------------------------------------------------------------------------------------
int main( int argc, char* argv[] )
{
    BSD_RND bsd_rnd;
    MS_RND ms_rnd;
 
    cout << "MS RAND:" << endl << "========" << endl;
    for( int x = 0; x < 10; x++ )
	cout << ms_rnd.rnd() << endl;
 
    cout << endl  << "BSD RAND:" << endl << "=========" << endl;
    for( int x = 0; x < 10; x++ )
	cout << bsd_rnd.rnd() << endl;
 
    cout << endl << endl;
    system( "pause" );
    return 0;
}
//--------------------------------------------------------------------------------------------------

Output:

SOURCE

Content is available under GNU Free Documentation License 1.2.