Monday, December 7, 2009

Random number generation

Understanding how random number generation (RNG) works

In java, lets say you wants to generate random number between i to j e.g.
[ i,j ) excluding upper limit. One standard pattern for accomplishing this is:

Min + (int)(Math.random() * ((Max - Min) + 1))


The java Math library function Math.random() generates a double value in the range [0,1). Notice this range does not include the 1.


In order to get a specific range of values first you need to multiply by the magnitude of the range of values you want covered.

Math.random() * ( Max - Min )


This returns a value in the range [0,Max-Min).


For example if you want [5,10] you need cover 5 integer values so you use

Math.random() * 5 This would return a value in the range [0,5)

Now you need to shift this range up to the range that you are targeting. You do this by adding the Min value.

Min + (Math.random() * (Max - Min))


You now will get a value in the range [Min,Max). Following our example, that means [5,10):

5 + (Math.random() * (10 - 5))


But, this is still doesn't include Max and you are getting a double value.
In order to get the Max value included, you need to add 1 to your range parameter (Max - Min) and then truncate the decimal part by casting to an int. This is accomplished via:

Min + (int)(Math.random() * ((Max - Min) + 1))


And there you have it. A random integer value in the range [Min,Max],
or per the example [5,10]:

5 + (int)(Math.random() * ((10 - 5) + 1))


How to get random numbers?

It's very difficult to get this right, and very, very easy to write an RNG which looks to produce random numbers but doesn't. If you are seriously interested in this, read Chapter 3 of Knuth's The Art of Computer Programming, otherwise use a library function.
There is a good article on wikipedia on the same.

Pseudo-random number generation in cpp

Provision for pseudo-random number generation is made by the following functions.
#include <stdlib .h>

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.
*/
#include <stdlib>
#include <time .h>
#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.

0 comments:

Post a Comment