A random number generator (often abbreviated as RNG) is a computational
or physical device designed to generate a sequence of numbers or symbols that lack any pattern, i.e. appear random. Computer-based systems for random number generation
are widely used, but often fall short of this goal, though they may meet some statistical tests for randomness intended to
ensure that they do not have any easily discernible patterns. Methods for generating random results have existed since ancient
times, including dice, coin flipping, the shuffling of playing cards, the use of yarrow stalks in the I Ching, and many other techniques.
The many applications
of randomness have led to many different methods for generating
data. These methods may vary as to how unpredictable or statistically
random they are, and how quickly they can generate random numbers.
Before the advent of computational random number generators, generating
large amount of sufficiently random numbers (important in statistics) required a lot of work. Results would sometimes be collected
and distributed as random number tables.
Pseudo-random number generators (PRNGs) are algorithms that can automatically create long runs (for example, millions of numbers long) with good random properties but eventually
the sequence repeats exactly (or the memory usage grows without bound). One of the most common PRNG is the linear congruential generator, which uses the recurrence
to generate numbers. The maximum number of numbers the formula can
produce is the modulus, m.
A simple pen-and-paper method for generating random numbers is the
so-called middle square method suggested by John Von Neumann. While simple to implement, its output is not guaranteed to be random.
A pen-and-paper method proven to generate truly random numbers exploits
the fact that the decimal expansion of the reciprocal 1/q will produce a stream of random numbers of length q - 1 if q is
such that q = 2S + 1 where S is a Sophie Germain prime, and both S and 2S + 1 are of the form 3, 9 or 11 mod 20. Thus “suitable”
prime numbers q are 7, 23, 47, 59, 167, 179, etc (corresponding to S = 3, 11, 23, 29, 83, 89, etc.). The result is a stream
of length q-1 digits (including leading zeros). So, for example, using q = 23 generates the random digits 0,4,3,4,7,8,2,6.....3,9,1,3
Example of a Random Number Generator