Implementation of random number generator [duplicate]

Question

Possible Duplicate:
How does a random number generator work?

I am looking for internal implementation of a random number generator in C/C++.Basically I am interested to know, what exactly happens when rand() is called. After all machine follows definite set of instructions, how can it be random!
Edit: Want to know how can I implement one in C/C++.

Answer 1

They're pseudo-random number generators, not truly random ones. This is often a good thing since it allows you to reproduce bugs more easily where "random" numbers are involved.

You can get random number generators, such as reading /dev/random under Linux but the normal ones that ship with C libraries generally aren't.

The simplest one are linear congruential generators where:

n(x+1) = n(x) * A + C modulo M

with suitably chosen values of A, C and M.

Wikipedia's page on LCGs gives some sample values used by various implementations. For example, the glibc one listed there has a = 1103515245, c = 12345, m = 2^31 so it's a simple thing like:

static unsigned int seed = 1;
void srand (int newseed) {
    seed = (unsigned)newseed & 0x7fffffffU;
}
int rand (void) {
    seed = (seed * 1103515245U + 12345U) & 0x7fffffffU;
    return (int)seed;
}

Aside: The glibc implementation still has this generator within it (called the Type 0 generator) but it also has a fancier trinomial generator as well, which is (presumably) better.

There are also more complex ones (such as the Mersenne twister) that have a much greater cycle time (time before starting to repeat).

Any truly random generator must use a truly random input source which is why /dev/random will sometimes block ("waiting for entropy") while /dev/urandom won't.

"Truly" random sources may be affected by timing between keystrokes, data entered by uers, the contents of network packets, disk I/O patterns, time taken for an ICMP response to come back over the network and all sorts of other wondrous, mostly non-deteministic things.

Unless you're heavily into crypto, normal random number generators will be just fine.

Answer 2

As I said in the comments, the random generators of RAM machines are not truly random, they are pseudo-random.

You can always have a look at the java source of java.util.Random.

Specifically - the method next(int bits) is what you are looking for.

protected int next(int bits) {
      long oldseed, nextseed;
      AtomicLong seed = this.seed;
      do {
            oldseed = seed.get();
            nextseed = (oldseed * multiplier + addend) & mask;
      } while (!seed.compareAndSet(oldseed, nextseed));
      return (int)(nextseed >>> (48 - bits));
}

(*) This answer fits for a previous version of the question, which was tagged as java and did not ask specifically for C++.

Answer 3

Here is a simple pseudo random algorithm:

//generates pseudo random series of numbers 0...RAND_MAX - 1 with uniform distribution, starting with 0

static const int A = 15342; // any number in (0, RAND_MAX)
static const int C = 45194; // any number in [0, RAND_MAX)
static const RAND_MAX = 100000;

int rand()
{
    static int prev = 0; //seed. any number in [0, RAND_MAX)
    prev = ( prev * A + C ) % RAND_MAX;
    return prev;
}

You can read more here: http://en.wikipedia.org/wiki/Linear_congruential_generator