2.5. Random numbers (class random_source)

Learning objectives

The class random_source

(Pseudo-)random numbers play an important role in many simulations, games, and last but not least in randomized algorithms, that is in algorithms whose efficiency is based on random decisions.

When we speak of pseudo-random numbers, we thereby take the circumstance into account that a deterministic computing machine, as our computer is, can never create something really random. It merely consists of a finite number of bits, therefore it has a finite number of configurations only, and therefore it must reach a configuration again, after a finite number of computing steps, in which it was some time before.[25] Its output repeats as of this time; the machine, therefore, is not “random” but deterministic.

Furthermore, it is very hard to define with mathematical exactness what “chance” really is. We do not want to go into this discussion here. The interested reader can look this up in [6].

Therefore, in the following, if we speak of random numbers, we actually mean pseudo-random numbers by that. We do not ask of these that they be random in the mathematical sense; rather, they should meet certain statistical criteria, for example that every (integer) number from a given interval be chosen from this interval with equal frequency.

LEDA has a class random_source for creating random numbers particularly comfortably. We will get to know this class in this section. It serves for creating random integer numbers from a certain interval (“integer mode”) and random bit strings of a length defined before (“bit mode”).

[25] Here we assume a finite input which is defined in advance. The user may not specify random input at runtime.