8.1 Problem

Random numbers are the numbers that occur, well, at random. Anyway, they are quite useful for programming. Chances are you will use them to solve some problems like those in Section 26.1 or Section 30.1.

But how do computers generate them. Surprise, they don’t. But then how could a Julia’s Random.jl (part of the standard library) generate one. Hmm, it’s complicated, but the basic idea could be explained with an example.

In a moment I will use a function that generates a random number in the range of 1 to 10 (inclusive-inclusive). Take a moment and try to guess it.

Ready, here we go.

getRand()

The number was seven. Did you guess it? If so, congrats. The popular psychology claims that for the said range people most often choose 7 and 3 so I wonder just how many of you, the readers, succeeded. Anyway, let me try again, I will use comprehensions to generate 10 random numbers and you will try to guess the next one, ready.

[getRand() for _ in 1:10]

[ 8, 9, 10, 1, 2, 3, 4, 5, 6, 7]

OK, what’s the next number?

You got it, it’s 8. Now let’s examine this sub-optimal number generator.

seed = 6

function getRand()::Int
    newSeed::Int = (seed % 10) + 1
    global seed = newSeed
    return newSeed
end

First, we declare a variable called seed with an initial, undisclosed and hard to predict value. From this seed our random numbers will sprout. Next, inside getRand we update the seed using some mathematical formula and return it as our result. Moreover, we update the old seed with that new value (global seed = newSeed, we use global since here seed is in the global scope). Thanks to the update the next time we use getRand it will return us some new value. Still, the function is purely deterministic as once you know the value of seed you can accurately predict the random variable you will get.

Surprisingly this is more or less what the random number generators do. The idea we got there was not bad, we just need to improve on its execution. We need a less obvious starting value, a more chaotic update method, and a much longer looping period so that no one sees that the sequence repeats itself periodically.

And here we are. In this chapter we are going to develop a simplified library for random numbers generation.

First, pick a random number generator that is relatively easy to implement (LCG seems to be good enough, but it’s up to you). The seed is often initialized with epoch time, e.g. the number of seconds that passed since 1 January 1970, which is kind of unpredictable. You should be able to get it out of the Dates module. Use the LCG to write getRand that returns a random Float64 in the range [0-1) (inclusive - exclusive). This is our bread and butter of random number generation. It works similar to JavaScript’s Math.random() or Julia’s rand() (Base.rand imports it from Random.jl). Next, define another getRand method, the one that returns a random integer from a given range. To cool down read about Box-Mueller transform and use it to define two getRandn methods, one that returns a value from a standard normal distribution with the mean = 0 and the standard deviation = 1 (like Base.randn do). The other should return a normal distribution with a specified mean and standard deviation.

If the above feels overwhelming, then proceed one step at a time and do as much as you can. Remember you need to understand this stuff enough to implement it in the code, leave the theorems and proofs to mathematicians and trust that they did their jobs right.