Random Numbers

One of the most difficult problems in computer science is implementing a truly random number generator. Because algorithms are deterministic, they cannot generate truly random numbers - except with the help of some outside device like processor-embedded circuits. Rather the numbers are generated with arithmetic operations, and, therefore, the sequences are not random but appear to be - hence, they are often called pseudo-random. At the turn of the 1950s D.H. Lehmer proposed an algorithm for generating random numbers. This algorithm is known as the linear congruential method, and since its inception it has quite firmly stood the test of time. This chapter further focuses on discrete finite distributions and random shuffling. In random shuffling, a random permutation is generated, where all permutations have a uniform random distribution. The design of a pseudo-random number generator must be done with great care - and this means that the user also has to understand the underlying limitations.