Glibc rand function implementation

Question

I am reading c the standard implementation of the rand () library with glibc source code. stdlib / random_r.c line 359

int __random_r (buf, result) struct random_data *buf; int32_t *result; { int32_t *state; if (buf == NULL || result == NULL) goto fail; state = buf->state; if (buf->rand_type == TYPE_0) { int32_t val = state[0]; val = ((state[0] * 1103515245) + 12345) & 0x7fffffff; state[0] = val; *result = val; } else { int32_t *fptr = buf->fptr; int32_t *rptr = buf->rptr; int32_t *end_ptr = buf->end_ptr; int32_t val; val = *fptr += *rptr; /* Chucking least random bit. */ *result = (val >> 1) & 0x7fffffff; ++fptr; if (fptr >= end_ptr) { fptr = state; ++rptr; } else { ++rptr; if (rptr >= end_ptr) rptr = state; } buf->fptr = fptr; buf->rptr = rptr; } return 0; fail: __set_errno (EINVAL); return -1; } 

I don’t understand how random_r generates a random number when (buf->rand_type != TYPE_0) , someone please explain? Thanks.

Answer 1

glibc rand() has two different generator implementations:

• A simple linear congruent generator (LCG) defined by the following equation:

  val = ((state * 1103515245) + 12345) & 0x7fffffff

  ( & 0x7fffffff discards the least significant random high bit)

  This is a very simple, single state LCG. This has some disadvantages. Most importantly, since it is a single-state generator, it does not fully generate a pseudo-random number for each individual rand() call. In fact, it is that it goes through the entire range (2 ^ 31) in a pseudo-random order . This makes sense: when you get a certain number, it means that you will not get this number again in the current period. You will get this number again exactly in the next call 2 ^ 31 rand() , no later, no later.

  This generator is called TYPE_0 in the glibc source.

• Somewhat more advanced, additive feedback generator. This generator has many states, which means that it does not have the "traverse property" described above. You can get the same number twice (or more times) for the same period.

  You can find a great description of this algorithm here .

  This generator is called TYPE_1 , TYPE_2 , TYPE_3 or TYPE_4 in the glibc source.

  Returning to your question, it generates values:

   seeding_stage() // (code omitted here, see the description from above link) for (i=344; i<MAX; i++) { r[i] = r[i-31] + r[i-3]; val = ((unsigned int) r[i]) >> 1; } 

  The code after else in your question is just the code above, but written in a different way (using pointers to an array containing the previous values).

Which generator is used depends on the size of the initial state with the initstate() function. The first (LCG) generator is used only with a size of 8 bytes. When it is larger, a second generator is used. When you set the seed using srand() , the default size is 128 bytes, so a second generator is used. Everything is written in the comments in the glibc source file you specified in your question.

Answer 2

In case someone else needs a simple implementation of the GNU C Library srand () / rand () functions, this C # class accurately reproduces the generated random numbers. The unchecked keyword is to explicitly allow integer overflows. (Based on the answer of Peter Yurkevich.)

 public class GnuRand { private uint[] r; private int n; public GnuRand(uint seed) { r = new uint[344]; unchecked { r[0] = seed; for (int i = 1; i < 31; i++) { r[i] = (uint)((16807 * (ulong)r[i - 1]) % 2147483647); } for (int i = 31; i < 34; i++) { r[i] = r[i - 31]; } for (int i = 34; i < 344; i++) { r[i] = r[i - 31] + r[i - 3]; } } n = 0; } public int Next() { unchecked { uint x = r[n % 344] = r[(n + 313) % 344] + r[(n + 341) % 344]; n = (n + 1) % 344; return (int)(x >> 1); } } } 

Answer 3

The two implementations are exactly the same, except that they use different random data.

TYPE_0 always uses magic numbers 1103515245 and 12345 along with the current state.

Otherwise, it uses magic numbers taken from the random data pool. Each time he is called, he goes a little further along the pool. As this happens, he replaces the data with new pseudo-random numbers based on the original ones, so that he gets new numbers when he turns around and starts walking again.