问题描述:

I am reading book called the c programming language by Brian W.Kernighan and Dennis M.Ritchie. I cannot understand the function that is written in the book for generating pseudo-random number it is like this;

`unsigned long int next = 1;`

int rand(void)

{

next = next * 1103515243 + 12345;

return (unsigned int)(next / 65536) % 32768;

}

void srand(unsigned int seed)

{

next = seed;

}

I also tried my self. But I only came up with the following observations

65536 = is the value of 16 bit unsigned + 1 bit

32768 = is the value of

16 bit signed + 1 bit

but I am not able to figure out the whole process .

This is the book written by the legends and I want to understand this book.

Please if anybody can help me to figure out this problem I will feel very very fortunate.

Pseudo Random Number Generators are a very complex subject. You could learn it for years, and get a PhD on it. As commented, read also about linear congruential generator (it looks like your code is an *example* in some C standard)

In C on POSIX systems, you have random(3) (and also lrand48(3), sort-of obsolete); In C++11 you have `<random>`

The `/65536`

operation might be compiled as `>>16`

a right shift of 16 bits.
The `%32768`

operation could be optimized as a bitmask (same as `&0x7fff`

) keeping 15 least bits.

This hasn't an accepted answer yet, so let's try one.

As noted by Basile Starynkevitch, what is implemented here is a pseudo-random number generator (RNG) from the class of linear congruential generators (LCGs). These in general take the form of a sequence

```
X := (a * X + c) mod m
```

The starting value for `X`

is called the *seed* (same as in the code). Of course `c < m`

and `a < m`

. Often also `a << c`

. Both `c`

and `m`

are usually large numbers chosen so that the whole sequence does reasonably well in the *spectral test*, but you probably don't have to care about that to understand the basic mode of operation. If you are a little bit into number theory, you will probably see that the sequence repeats after a while (it is periodic).

Random numbers are generated, by first seeding `X`

with a starting seed. For each generated number, the sequence is cycled and a subset of the bits of `X`

are returned.

In the code from the question, `a = 1103515245`

, `c = 12345`

, and
`m`

is implicitly `pow(2, 8 * sizeof(unsigned long))`

by virtue of unsigned integer overflow. These are also the values ISO/IEC 9899, i.e. the C language standard suggests.

With this known, the first pitfall is probably this statement:

```
return (unsigned int)(next / 65536) % 32768;
```

Kernighan and Ritchie probably thought that using only simple arithmetic is more readable and more portable than using bit masks and bit shifts. The above is equivalent to

```
return (unsigned int)(next >> 16) & 0x7fff
```

which selects bits 16-30 from `next`

. You get back a pseudo-random number in the range `[0;32767]`

. The bit range is also the one suggested in the C standard.

**WARNING**: It is well known that this LCG does --while widely deployed, because it's noted in the standard-- not produce very good pseudo-random numbers (the version in GLIBc is even worse). Distinctively, it is absolutely unsafe to use for cryptographic applications. With the few number of random bits, I would not even use it for any Monte Carlo method, because results may be severely skewed by the quality of the RNG.

So in short: Try to understand it: yes, you are welcome. Use it for anything: no.