CODEWITHSUNDEEP
c++c
Shivank Sagar
Shivank Sagar

Reputation: 42

pseudo-random function in c?

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.

Upvotes: 3

Views: 4802

Answers (2)

dhke
dhke

Reputation: 15398

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.

Upvotes: 6

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

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.

Upvotes: 4

Related Questions