What is the distribution for random() in stdlib?

Question

The man page claims that the random function in the C standard library "returns a value between 0 and RAND_MAX."

Unfortunately, it does not say what the distribution is for this random function. Empirically, we can measure it to be uniform, but without documentation, I cannot be certain it will never change when I use it in applications.

Is the distribution documented anywhere?

Answer 1

Neither the C standards nor the POSIX specifications define a distribution for random() or rand(). The manpages for a few systems I checked don't appear to define this either.

I think it's very safe to assume, with the computers that you encounter, that random() and rand() will produce random numbers which accumulate to (approximately) a uniform distribution, however you can test this empirically if you are unsure.

In general, I think if you promise to generate a random number in a range, it is assumed that (as the quantity of numbers goes to infinity) they should accumulate to a uniform distribution, otherwise you lose some randomness (loss of entropy). In my experience, the only time you mention a distribution for a random number generator is if it's something other than uniform (e.g., they might tell you that some specific PRNG will produce random numbers according to a normal distribution).

Edit (POSIX)

While verifying my assumptions, I ran across a POSIX family of functions that are defined to generate random numbers in a uniform distribution:

NAME

drand48, erand48, jrand48, lcong48, lrand48, mrand48, nrand48, seed48, srand48 - generate uniformly distributed pseudo-random numbers

SYNOPSIS

#include <stdlib.h>

double drand48(void);
double erand48(unsigned short xsubi[3]);
long jrand48(unsigned short xsubi[3]);
void lcong48(unsigned short param[7]);
long lrand48(void);
long mrand48(void);
long nrand48(unsigned short xsubi[3]);
unsigned short *seed48(unsigned short seed16v[3]);
void srand48(long seedval);

FreeBSD's manpage for drand48 does note that they are not cryptographically secure, and that arc4random() is recommended for cryptographic applications. arc4random() is from BSD but has been ported to other systems -- it is defined to produce a uniform distribution.

Answer 2

The random(void) function is not part of the C Standard. However, (@nwellnhof!) it is part of the POSIX standard.

It is documented in the glibc documentation and in POSIX. However, no distribution is guaranteed by either text.

glibc:

long int random(void)

Preliminary:|MT-Safe|AS-Unsafe lock|AC-Unsafe lock|SeeSection 1.2.2.1[POSIX Safety Concepts], page 2.

This function returns the next pseudo-random number in the sequence. The value returned ranges from 0 to 2147483647.

NB: Temporarily this function was defined to return a int32_t value to indicate that the return value always contains 32 bits even if long int is wider. The standard demands it differently. Users must always be aware of the 32-bit limitation, though.

POSIX:

The random() function uses a non-linear additive feedback random-number generator employing a default state array size of 31 long integers to return successive pseudo-random numbers in the range from 0 to 2^31-1. The period of this random-number generator is approximately 16 x (2^31-1). The size of the state array determines the period of the random-number generator. Increasing the state array size increases the period.

With 256 bytes of state information, the period of the random-number generator is greater than 2^69.

Like rand(), random() produces by default a sequence of numbers that can be duplicated by calling srandom() with 1 as the seed.

The srandom() function initialises the current state array using the value of seed.

The initstate() and setstate() functions handle restarting and changing random-number generators. The initstate() function allows a state array, pointed to by the state argument, to be initialised for future use. The size argument, which specifies the size in bytes of the state array, is used by initstate() to decide what type of random-number generator to use; the larger the state array, the more random the numbers. Values for the amount of state information are 8, 32, 64, 128, and 256 bytes. Other values greater than 8 bytes are rounded down to the nearest one of these values. For values greater than or equal to 8, or less than 32 random() uses a simple linear congruential random number generator. The seed argument specifies a starting point for the random-number sequence and provides for restarting at the same point. The initstate() function returns a pointer to the previous state information array.

If initstate() has not been called, then random() behaves as though initstate() had been called with seed=1 and size=128.

If initstate() is called with 8 <= size <32, then random() uses a simple linear congruential random number generator.

Once a state has been initialised, setstate() allows switching between state arrays. The array defined by the state argument is used for further random-number generation until initstate() is called or setstate() is called again. The setstate() function returns a pointer to the previous state array.

However, if you're using GLIBC, and you want a pseudorandom number function that is guaranteed by standard to produce a uniformly distributed random number over its range then you can use the SVID random functions, lrand48 and friends:

From page 330:

The functions lrand48() and nrand48() return non-negative long integers uniformly distributed over the interval [ 0 , 2^31).

These are also defined by POSIX as well.