Category Archives: algorithms and data structures

Linear congruential generator

Screen Shot 2014-10-25 at 12.57.39 PM

 

C

#include 
 
/* always assuming int is at least 32 bits */
int rand();
int rseed = 0;
 
inline void srand(int x)
{
	rseed = x;
}
 
#ifndef MS_RAND
#define RAND_MAX ((1U << 31) - 1)
 
inline int rand()
{
	return rseed = (rseed * 1103515245 + 12345) & RAND_MAX;
}
 
#else /* MS rand */
 
#define RAND_MAX_32 ((1U << 31) - 1)
#define RAND_MAX ((1U << 15) - 1)
 
inline int rand()
{
	return (rseed = (rseed * 214013 + 2531011) & RAND_MAX_32) >> 16;
}
 
#endif/* MS_RAND */
 
int main()
{
	int i;
	printf("rand max is %d\n", RAND_MAX);
 
	for (i = 0; i < 100; i++)
		printf("%d\n", rand());
 
	return 0;
}

C++

#include 
 
//--------------------------------------------------------------------------------------------------
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
MS RAND:
========
38
7719
21238
2437
8855
11797
8365
32285
10450
30612

BSD RAND:
=========
12345
1406932606
654583775
1449466924
229283573
1109335178
1051550459
1293799192
794471793
551188310

UNIX Shell

#! /bin/bash
 
function BSD() {
  SEED=$(((1103515245 * $SEED + 12345) % 2**31))
  echo "  $SEED"
}
 
function MS() {
  SEED=$(((214013 * $SEED + 2531011) % 2**31))
  echo "  $(($SEED / 2**16))"
}
 
function output() {
  SEED=0
  echo "$1"
 
  for i in {1..10}; do
    eval "$1"
  done
 
  echo ""
}

BSD
12345
1406932606
654583775
1449466924
229283573
1109335178
1051550459
1293799192
794471793
551188310

MS
38
7719
21238
2437
8855
11797
8365
32285
10450
30612