Implementation of random number generator

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

Because it's not really random: http://en.wikipedia.org/wiki/Pseudorandom_number_generator — Averroes, Aug 14 '12 at 06:07
http://en.wikipedia.org/wiki/Linear_congruential_generator. C++11 lets you use Mersenne twisters etc, too, with ``, which work out a whole lot better. — chris, Aug 14 '12 at 06:08
Other closely related questions: http://stackoverflow.com/questions/584566/pseudo-random-number-generator, http://stackoverflow.com/questions/7114043/random-number-generation-in-c11-how-to-generate-how-do-they-work — jogojapan, Aug 14 '12 at 06:13

paxdiablo · Accepted Answer · 2022-12-03T07:59:05.483

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 users, 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-deterministic things.

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

Andrew · Answer 2 · 2014-06-16T15:58:35.133

2

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

edited Jun 16 '14 at 15:58

answered Aug 14 '12 at 06:16

Andrew

24,218
13
61
90

Those are very poorly chosen values for A, C and RAND_MAX by the way. All your numbers will be multiples of 5000 :-) Relatively prime numbers tend to give a better distribution. – paxdiablo Aug 14 '12 at 06:20
@paxdiablo: agree, randomized them a bit ) But in any case it will give a uniform distribution. Choosing good numbers require more research – Andrew Aug 14 '12 at 06:23
That static var `prev` does not seem to ever be updated. – jjmontes Jun 16 '14 at 15:50

score 1 · Answer 3 · answered Aug 14 '12 at 06:14

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

Implementation of random number generator

3 Answers3

Linked