5.1 Random Numbers

All the designs we presented so far were the result of completely predictable processes. However, if we want to use computers to design and the intended design requires randomness, then we must be able to incorporate it in our algorithms. In practice, randomness can be incorporated in various ways, for example:

• An object’s color may be chosen randomly;

• The length of a wall can be a random value between certain limits;

• The decision to divide an area or keep it whole can be random;

• The shape of a given architectural element can be chosen randomly.

In any of the above cases, we can simulate the intended randomness by using numbers chosen within certain limits.

• To produce a random color, we can randomly generate three numbers representing the RGB values of that color; RGB stands for Red Green Blue, a model where any color can be seen as the composition of the three additive primary colors (red, green and blue).

• To produce a random length, we can generate a random number within that length’s limits;

• For a logical decision (such as the one of choosing whether to divide a wall or not), we can emulate tossing a coin by randomly generating either zero or one, and treat zero as heads and one as tails;

• For a random choice among a set of alternatives (such as the shape of a given architectural element), we can simply generate a random number between one and the number of alternatives and then choose the one corresponding to the randomly generated number.

These examples show us that the ability to generate a random number within a certain range is sufficient to implement many different random processes.

There are two fundamental processes for generating random numbers. The first one is based on the measurement of physical processes which are intrinsically random, such as electronic noise or radioactive decay. The second process is based on the use of arithmetic functions that, given an initial value (called the seed), produce a sequence of seemingly random numbers, where the generation of each number is based on the previous one. In the first case, we are dealing with a true-random number generator, while in the latter case, we are talking about a pseudo-random number generator. The term pseudo is due to the fact that the generated sequence of numbers is not really random: if we repeat the value of the original seed we will also repeat the sequence of generated numbers.

Although a pseudo-random number generator produces a sequence of numbers that are actually not random, it has two important advantages:

• It can be easily implemented using any programming language, not requiring any other additional mechanisms to obtain the randomness source;

• It can be useful to detect and correct bugs in our programs. In fact, in order to identify the cause of a bug, it may be necessary to exactly reproduce the same conditions that led to that bug. Besides that, after fixing the bug it is often necessary to rerun the program to make sure that the bug no longer occurs. Unfortunately, when the program’s behavior depends on a truly random sequence of numbers, it is impossible to reproduce the exact same conditions: the next time we run the program, the sequence of numbers will almost certainly be different.

Therefore, from now on, we will only consider pseudo-random number generators, which we will abusively designate as random number generators. A generator of this kind is characterized by a function \(f\) that, given a certain argument \(x_i\), produces a number \(x_{i+1}=f(x_i)\), apparently unrelated to \(x_i\). The seed of the generator is the element \(x_0\) of the sequence.

What is left now is to find a suitable \(f\) function. For this, and among other qualities, it is required that the numbers generated by \(f\) are equiprobable, i.e., all numbers within a certain range are equally probable to be generated. Moreover, it is also demanded that the period of the generated numbers sequence is as large as possible, i.e., the sequence of numbers only starts to repeat itself after the generation of a large amount of numbers.

Numerous functions with these characteristics have been studied up to now. The most used is called the linear congruential generator function, which has the form:

\[x_{i+1} = (a x_i + b)\bmod m\]

The mathematical operation modulo (\(p\bmod q\)) corresponds to the remainder of the division of the first operand (the dividend \(p\)) by the second operand (the divisor \(q\)), having the same sign as the divisor. In Julia, the same behavior is implemented by the operator %, and by the functions mod and rem.

For example, if we have \(a = 25173\), \(b = 13849\), and \(m = 65536\), and we begin the sequence with an arbitrary seed, for example, \(x_0=12345\), we obtain the following pseudo-random numbers:

2822, 11031, 21180, 42629, 27202, 49667, 50968, 33041, 37566, 43823, 2740, 43997, 57466, 29339, 39312, 21225, 61302, 58439, 12204, 57909, 39858, 3123, 51464, 1473, 302, 13919, 41380, 43405, 31722, 61131, 13696, 63897, 42982, 375, 16540, 25061, 24866, 31331, 48888, 36465,... Actually, this sequence is not random enough as there is a pattern that repeats itself continuously. Can you discover it?

We can easily confirm these results using Julia:

This approach, however, implies that we can only generate a “random” number \(x_{i + 1}\) if we recall the \(x_i\) number generated immediately before, so that we can provide it as an argument for the next_random_number function. Unfortunately, the moment and the point of the program at which we might need a new random number can occur much later and much further than the moment and the point of the program when the last random number was generated, which substantially complicates the program’s writing. It would be preferable that, instead of having a next_random_number function that depends on the previously generated number \(x_i\), we had a random_number function that did not need the previously generated number to be able to produce the next one. This way, at any point of the program where we might need to generate a new random number, we would only have to invoke the random_number function without having to recall the previously generated number. Starting with the same seed value, we would have:

> random_number()

2822

> random_number()

11031

> random_number()

21180

In the next section we will describe how to define the random_number function.