5.3 Random Choices
Observing the next_random_number function definition, we find that its last operation is computing the remainder of the division by \(65536\), which implies that the function always produces values between \(0\) and \(65535\). Although (pseudo) random, these values are contained in a range that will rarely be useful, as it is much more frequent that we need random numbers that are contained in much smaller intervals. For example, if we want to simulate the action of flipping a coin, we are only interested in randomly generating the numbers \(0\) or \(1\), representing “heads” or “tails”.
Just as our random_number function is limited to the range \([0,65536[\) by the remainder of the division by \(65536\), we can apply the same operation to produce smaller ranges. Therefore, in the case of flipping a coin, we can simply use the random_number function to generate a random number and then compute the remainder of its division by \(2\). Generalizing, when we want random integer numbers in an interval \([0,x[\), we apply the remainder of the division by \(x\). Thus, we can define a new function that generates a random number between zero and a parameter, which we will call random:
random(x) = random_number()%x
Note that the random function should never receive an argument greater than \(65535\) because that would make the function lose the equiprobability feature of the generated numbers: all numbers greater than \(65535\) will have zero probability of occurring. In fact, the argument of the random function should be fairly below the limit of the random function to maintain the equiprobability of the results.
It is now possible to simulate a number of random phenomena such as, for example, flipping a coin:
heads_or_tails() = random(2) == 0 ? "heads" : "tails"
Unfortunately, when repeatedly tested, our function does not seem very random:
> heads_or_tails()
"tails"
> heads_or_tails()
"heads"
> heads_or_tails()
"tails"
> heads_or_tails()
"heads"
> heads_or_tails()
"tails"
> heads_or_tails()
"heads"
In fact, the results we are getting are a constant repetition of the pair: heads/tails, which reveals that the expression random(2) merely generates the following sequence:
0101010101010101010101010101010101010101010101010101010101
The same phenomenon occurs for other intervals: for example, the expression random(4) should generate a random number from the set \(\{0,1,2,3\}\), but its repeated invocation generates the following sequence of numbers:
0123012301230123012301230123012301230123012301230123012301
Despite the numbers being perfectly equiprobable, they are clearly not random.
The problem in both previous sequences is the fact that they have a very small period. The period is the number of elements that are generated before the sequence enters into a cycle and starts repeating the same elements previously generated. Obviously, the greater the period, the better the random number generator will be. In that sense, the one we have been using is of poor quality.
Great amounts of effort have been invested on finding good random number generators and, although the better ones are produced using fairly more sophisticated methods than the ones we have used so far, it is also possible to find a good linear congruential generator as long as we wisely choose the parameters. In fact, the linear congruential generator \[x_{i+1} = (a x_i + b) \bmod m\] can be a good pseudo-random generator as long as we have \(a=16807\), \(b=0\) and \(m=2^{31}-1=2147483647\). A direct translation of this mathematical definition to Julia produces the following function:
next_random_number(number) = (16807*number)%2147483647
Using this new definition, the repeated evaluation of the random(2) expression produces the following sequence:
01001010001011110100100011000111100110110101101111000011110
and the repeated evaluation of the random(4) expression produces:
21312020300221331333233301112313001012333020321123122330222
It is fairly clear that the generated sequences now have a period large enough for any repetition pattern to be detected. Thus, from now on, this is the definition of the next_random_number function that will be used.
5.3.1 Random Fractional Numbers
The process of generating random numbers previously implemented is only able to generate random integer numbers. However, we often need to generate fractional random numbers in an arbitrary interval \([0, x[\), for example \([0, 1[\), which would generate numbers such as 0.05, 0.0123, etc.
To this end, the random function can analyze its argument \(x\) to determine whether it is an integer or a real, and then return a random value of the appropriate type. Finally, to ensure that the number is in the appropriate range, we need to map the generator interval, which is \([0,2147483647 [\), in the interval \([0,x[\). The implementation is the following: This function uses the isa Julia’s function that tests whether an element is of a given type, such as integer numbers (which are represented by Int).
random(x) = x isa Int ? random_number()%x : x*random_number()/2147483647.0
We can now apply the random function to produce either integer or real numbers:
> random(10)
2
> random(10.0)
3.4854938618305575
Given its utility, the random function is already predefined in Khepri.
5.3.2 Random Numbers within a Range
Sometimes, instead of generating random numbers in the range \([0, x[\), we prefer to generate random numbers in the range \([x_0, x_1[\). In this case, we just have to generate a random number within \([0, x_1-x_0[\) and then add \(x_0\). The random_range function implements this behavior:
random_range(x0, x1) = x0+random(x1-x0)
Like the random function, the random_range function also produces a real value when any of the limits is a real number. The random_range function is also predefined in Khepri.
As an example, let us reconsider the tree function that models a tree, defined in section the Recursion in Nature as:
tree(p, l, a, da0, f0, da1, f1) =
let top = p+vpol(l, a)
branch(p, top)
if l < 0.1
leaf(top)
else
tree(top, l*f0, a+da0, da0, f0, da1, f1)
tree(top, l*f1, a-da1, da0, f0, da1, f1)
end
end
To incorporate some randomness in this tree model, we can consider that both the branches’ opening angles and length reduction factors can vary throughout the recursion process. Thus, instead of worrying about having different opening angles and factors for the left and right branches, we will simply have random variations on both sides:
tree(p, l, a, min_a, max_a, min_f, max_f) =
let top = p+vpol(l, a)
branch(p, top)
if l < 0.2
leaf(top)
else
tree(top,
l*random_range(min_f, max_f),
a+random_range(min_a, max_a),
min_a,
max_a,
min_f,
max_f)
tree(top,
l*random_range(min_f, max_f),
a-random_range(min_a, max_a),
min_a,
max_a,
min_f,
max_f)
end
end
Using this new version, we can generate several similar trees yet sufficiently different to seem much more natural. The trees shown in this figure were generated using exactly the same parameters:
tree(xy(0, 0), 2, pi/2, pi/16, pi/4, 0.6, 0.9)
tree(xy(15, 0), 2, pi/2, pi/16, pi/4, 0.6, 0.9)
tree(xy(30, 0), 2, pi/2, pi/16, pi/4, 0.6, 0.9)
tree(xy(0, 15), 2, pi/2, pi/16, pi/4, 0.6, 0.9)
tree(xy(15, 15), 2, pi/2, pi/16, pi/4, 0.6, 0.9)
tree(xy(30, 15), 2, pi/2, pi/16, pi/4, 0.6, 0.9)
Various trees created with the branches’ opening angles varying in the interval \([\frac{\pi}{16},\frac{\pi}{4}[\) and the length reduction factors varying in the interval \([0.6,0.9[\).
5.3.3 Exercises 27
5.3.3.1 Question 77
The trees produced by the tree function are unrealistic because they are completely two-dimensional, with branches that are simple lines and leaves that are small circles. The calculation of the branches and leaves’ coordinates is also two-dimensional, relying on polar coordinates specified by the length and angle parameters.
Redefine the branch, leave and tree functions in order to increase the realism of the generated trees.
To simplify, assume that the leaves can be simulated by small spheres and that the branches can be simulated by truncated cones with the base radius being \(10\%\) of the branch’s length and the top radius being \(90\%\) of the base radius.
For the generation of trees to be truly three-dimensional, redefine the tree function so that the top of each branch is a point in spherical coordinates chosen randomly from the base of the branch. This implies that the tree function’s parameters of the polar coordinates (length and angle) will have to be replaced by the parameters of the spherical coordinates (length, longitude and colatitude). Therefore, instead of receiving the four limits for generating random lengths and angles, the tree function will receive six limits for generating random lengths, longitudes and colatitudes.
Try different arguments in your redefinition of the tree function, in order to create something similar to the image below:
5.3.3.2 Question 78
Define a function named random_cylinder that receives as argument a number of cylinders \(n\), generating as a result \(n\) cylinders placed in random positions, with random radii and lengths, as presented in the following image:
5.3.3.3 Question 79
A random walk is a formalization of an object motion that is subject to impulses of random magnitude and direction. This phenomenon happens, for example, to a grain of pollen when falling into water: as the molecules of water bump into the grain, it will randomly move.
The following image present three random walks:
Consider a model of a random walk in a two-dimensional plane. Define the random_walk function that has as parameters the starting point \(P\) of the walk, the maximum distance \(d\) the object can move when impulsed, and the \(n\) number of successive impulses the object will receive. Note that, on each impulse, the object moves in a random direction, with a random distance between zero and the maximum distance.
This function should simulate the corresponding random walk, as presented in the previous figure, which was created with three different executions of this function. From left to right, the following parameters were used: \(d=5\) and \(n=100\); \(d=2\) and \(n=200\); and \(d=8\) and \(n=50\).
5.3.3.4 Question 80
Define a biased heads_or_tails function such that, even though it randomly produces the strings "heads" or "tails", the "heads" string falls, on average, only \(30\%\) of the times the function is executed.
5.3.3.5 Question 81
Define the cylinder_sphere function that, given a point \(P\), a length \(l\), a radius \(r\), and a number \(n\), creates \(n\) cylinders, of length \(l\) and radius \(r\), with the base centered at the point \(P\) and with the top positioned randomly, as presented in the following image:
5.3.3.6 Question 82
Define a function called connected_blocks that builds a cluster of connected blocks, i.e., blocks are linked together, as presented in the following figure:
Note that the adjacent blocks always have orthogonal orientations.