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++.
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.
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++.
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
