Sunday, December 6, 2009

Random number generation

Provision for pseudo-random number generation is made by the following functions.

int rand(void);
void srand(unsigned int seed);
Rand returns a pseudo-random number in the range 0 to RAND_MAX, which has a value of at least 32767.
Srand allows a given starting point in the sequence to be chosen according to the value of seed. If srand is not called before rand, the value of the seed is taken to be 1. The same sequence of values will always be returned from rand for a given value of seed.
The Standard describes an algorithm which may be used to implement rand and srand. In practice, most implementations will probably use this algorithm.

 Random numbers are useful in programs that need to simulate random events, such as games, simulations and experimentations. In practice no functions produce truly random data -- they produce pseudo-random numbers. These are computed form a given formula (different generators use different formulae) and the number sequences they produce are repeatable. A seed is usually set from which the sequence is generated. Therefore is you set the same seed all the time the same set will be be computed.
One common technique to introduce further randomness into a random number generator is to use the time of the day to set the seed, as this will always be changing.
There are many (pseudo) random number functions in the standard library. They all operate on the same basic idea but generate different number sequences (based on different generator functions) over different number ranges.

rand() returns successive pseudo-random numbers in the range from 0 to (2^15)-1.
srand() is used to set the seed. A simple example of using the time of the day to initiate a seed is via the call:
srand( (unsigned int) time( NULL ));
The following program card.c illustrates the use of these functions to simulate a pack of cards being shuffled:

** Use random numbers to shuffle the "cards" in the deck. The second
** argument indicates the number of cards. The first time this
** function is called, srand is called to initialize the random
** number generator.
#define TRUE 1
#define FALSE 0

void shuffle( int *deck, int n_cards )
int i;
static int first_time = TRUE;

** Seed the random number generator with the current time
** of day if we haven't done so yet.
if( first_time ){
first_time = FALSE;
srand( (unsigned int)time( NULL ) );

** "Shuffle" by interchanging random pairs of cards.
for( i = n_cards - 1; i > 0; i -= 1 ){
int where;
int temp;

where = rand() % i;
temp = deck[ where ];
deck[ where ] = deck[ i ];
deck[ i ] = temp;
There are several other random number generators available in the standard library:

double drand48(void);
double erand48(unsigned short xsubi[3]);
long lrand48(void);
long nrand48(unsigned short xsubi[3]);
long mrand48(void);
long jrand48(unsigned short xsubi[3]);
void srand48(long seed);
unsigned short *seed48(unsigned short seed[3]);
void lcong48(unsigned short param[7]);
This family of functions generates uniformly distributed pseudo-random numbers.
Functions drand48() and erand48() return non-negative double-precision floating-point values uniformly distributed over the interval [0.0, 1.0).
Functions lrand48() and nrand48() return non-negative long integers uniformly distributed over the interval [0, 2**31).
Functions mrand48() and jrand48() return signed long integers uniformly distributed over the interval [-2**31, 2**31).
Functions srand48(), seed48(), and lcong48() set the seeds for drand48(), lrand48(), or mrand48() and one of these should be called first.

No comments:

Post a Comment