2

Possible Duplicate:
How does a random number generator work?

How does C compiler takes decisions whether which number should be generated next in a random number generation function? For example it always generates a new random number between the given range. How is that done?

Community
  • 1
  • 1
Afaq
  • 1,146
  • 1
  • 13
  • 25
  • The problem I've noticed is every time you run your program same sequence of random numbers are generated. Hence, seeds come in. – जलजनक Oct 14 '12 at 18:27
  • Read this: [Random number generator in C](http://stackoverflow.com/questions/12885171/logic-behind-the-random-number-generator-in-c) – P.P Oct 14 '12 at 18:30

6 Answers6

1

It depends on the specific implementation of the pseudo random number generator (PRNG) in question. There are a great many variants in use.

A common example is the family of linear congruential generators (LCGs). These are defined by a recurrence relation:

   Xn+1 <- aXn + c (mod m)

So each new sample from the PRNG is determined solely by the previous sample, and the constants a, c and m. Note that the choice of a, c and m is crucial, as discussed here.

LCGs are very simple and efficient. They are often used for the random number generators provided by the standard library. However, they have poor statistical properties and for better randomness, more advanced PRNGs are preferred.

David Heffernan
  • 601,492
  • 42
  • 1,072
  • 1,490
1

It generates the next number by keeping some state and modifying the state every time you call the function. Such a function is called a pseudorandom number generator. An old method of creating a PRNG is the linear congruential generator, which is easy enough:

static int rand_state;
int rand(void)
{
    rand_state = (rand_state * 1103515245 + 12345) & 0x7fffffff;
    return rand_state;
}

As you can see, this method allows you to predict the next number in the series if you know the previous number. There are more sophisticated methods.

Various types of pseudorandom number generators have been designed for specific purposes. There are secure PRNGs which are slow but hard to predict even if you know how they work, and there are big PRNGs like Mersenne Twister which have nice distribution properties and are therefore useful for writing Monte Carlo simulations.

As a rule of thumb, a linear congruential generator is good enough for writing a game (how much damage does the monster deal) but not good enough for writing a simulation. There is a colorful history of researchers who have chosen poor PRNGs for their programs; the results of their simulations are suspect as a result.

Dietrich Epp
  • 205,541
  • 37
  • 345
  • 415
1

It is not a compiler but a C library that has a function to produce pseudorandom (not truly random!) numbers.

Usually linear congruential generators are used for this.

qrdl
  • 34,062
  • 14
  • 56
  • 86
1

Well, the C compiler doesn't take that decison. The next random number depends on the algorithm. Generating random number is not an easy task. Take a look at

Pablo
  • 13,271
  • 4
  • 39
  • 59
0

There are many questions regarding this in stackoverflow. Here are few. You can take help from these.

implementation of rand()

Rand function in c

Rand Implementation

Community
  • 1
  • 1
taufique
  • 2,701
  • 1
  • 26
  • 40
0

This is actually a really big topic. Some of the key things:

  • Random number generation is done at run-time, rather than compile-time.
  • The strategy for providing randomness depends (or should depend) greatly on the application. For example, if you simply need a sequence of values that are evenly distributed throughout the given range, solutions such as a linear congruential generator are used. If your application is security/cryptography related, you'll want the stronger property that your values are both randomly distributed and also unpredictable.
  • A major challenge is acquiring "real" randomness, which you can use to seed your pseudorandom generator (which "stretches" real randomness into an arbitrary amount of usable randomness). A common technique is to use some unpredictable system state (e.g., sample the location of the mouse, or keypress timing) and then use a pseudorandom generator to provide randomness to the system as a whole.
mfsiega
  • 2,852
  • 19
  • 22