Generating Random Numbers

If you’ve used Python, or any high-level programming language for that matter, it’s easy to take for granted that you can use it to generate random numbers. For example, you can print a random integer from 1 through 10 with the following snippet:

But here’s a fundamental, almost philosophical, question: how can a computer choose a random number? Here’s what I mean.

Let’s talk about randomness as it appears in the world. If I ask my friend to choose a random number between 1 and 10, is the number they choose truly random? Perhaps there’s some psychology involved in the number they choose. In fact, some studies show that people choose 7 more often than any other number. While there’s debate as to why that’s so, it indicates that a human choosing a random number is not as random as we might think. After all, if the process was truly random, 7 should be as common a choice as any other number.

Let’s consider possibly the most “classic” of all random activities: flipping a coin. Is it truly random to flip a coin to see whether it lands on heads or tails? In theory, physicists should be able to predict the result by measuring the strength one used to flip the coin, plus the weight of the coin, plus the air pressure, plus the hardness of the surface on which the coin lands, plus a few other factors. Indeed, if we want to get really philosophical, we can wonder whether anything in the world is truly random.

Despite these arguments, we can still define randomness in a way that is good enough for our purposes.

Here’s the deal. Sure, it might be technically possible to predict the outcome of a coin toss. However, it’s really difficult to measure all the relevant factors—and you and I certainly aren’t going to do so. Therefore, we can consider flipping a coin to be unpredictable enough to be called random. And so, we can say that an event is random if it’s difficult to predict the outcome.

But now let’s get back to computers. A computer doesn’t flip coins and certainly doesn’t use original thinking to generate a random number “off the top of its head.” A computer is what’s called deterministic, meaning that it’s only capable of receiving and executing instructions we give it. So, if we give the computer an algorithm to generate a random number, say, using mathematical calculations, we’ll still be able to predict exactly what number the computer will choose if we know the algorithm. It won’t be random at all.

This is a real head-scratcher. Is it even possible for a computer to choose a random number?

It turns out that there are two different ways in which a computer generates random numbers: with a True Random Number Generator (TRNG) or a Pseudorandom Number Generator (PRNG). We’ll take a look at both, starting with TRNG.

True Random Number Generators

A TRNG uses a highly unpredictable external source rather than an algorithm to provide a random number. That is, since a computer is completely deterministic and cannot come up with a random number on its own, the computer relies on this outside source to do so.

This outside source could be anything in nature or the environment that is so hard to predict that we consider it random. For example, we could connect the computer to a secret office in a basement in South Dakota (the epicenter of secret basement offices). Each time the computer needs a random number, it sends a signal to that office, and someone there will roll a die, which we’d consider a random event. The number that the die lands on is then sent back to the computer.

Of course, this is completely impractical. However, here are some TRNGs that are used in real life. In truth, some of them may sound almost as ridiculous as our South Dakota example, yet they are truly used in the real world.

• You know how if you set a radio to the wrong channel, you hear nothing but static noise? This static is generated by lightning strikes and other natural processes. One TRNG technique is to connect the computer to a radio that’s set to a channel that picks up this static. The computer then picks out the frequency of sound at a precise moment in time and uses that frequency to generate the random number. As crazy as this sounds, this is currently one of the more popular TRNGs out there.

• Another real-life TRNG approach is to hook a computer up to a camera that takes a snapshot of a lava lamp, and generates a random number based on the exact formation of the “lava” at that given moment. I kid you not.

• Yet another TRNG connects the computer to decaying radioactive material. It’s hard to predict the exact way in which an atomic nucleus decays, so why not use that for generating random numbers? (Don’t try this at home.)

These are considered true random number generators because the random numbers are based on processes that are too difficult to predict. They’re the best source for generating the “randomest” numbers.

However, there are two major disadvantages to TRNGs. First, they’re not always practical, as you can imagine. Second, it can be relatively slow to generate a random number based on an external process, at least compared with PRNGs, which we’ll look at soon.

Interestingly, there exist online TRNG services that allow you to connect your code to their TRNG devices via a web API. That is, they have computers hooked up to lava lamps or radioactive material or whatever, and all you have to do is connect to their servers and grab a truly random number that they generate. While this may help with the practicality issue, making a web request is way slower than having your computer generate a random number internally.

Because of these issues of practicality and speed, Python uses a PRNG rather than a TRNG. On that note, let’s look at how PRNGs work.

Pseudorandom Number Generators

My dictionary tells me that the prefix pseudo means “false, not genuine, a sham.” Indeed, pseudorandom numbers are just that—a total sham. They’re not random at all; they only seem random. Yet, this is exactly the approach that Python and most other programming languages use to generate “random” numbers. Let’s see how this works.

Prepared Sequence

The main idea behind PRNGs is that they have a prepared sequence of numbers that, at first glance, seem random. For example:

When looking at these numbers at a glance, they do look kind of random. At least, there’s no predictable pattern.

With a PRNG, each time we ask the computer to generate a “random” number, it will use this sequence. The first time we execute code that generates a random number, the computer will return the first number from the sequence. In our example, this would be the number 5. The next time we ask the computer to generate a random number, it will return 9 since it’s the next integer in the sequence. And the third time we ask for a random number, the computer will return 1. You get the idea.

When the computer reaches the end of the sequence (the final 2 in our example), it will then start all over again at the beginning of the sequence. There are 20 integers in the example sequence, so when we generate a random number for the 21st time, we’ll get back a 5 since it’s the first number in the sequence.

If you’re horrified at this algorithm for generating random numbers, you should be. This isn’t random at all! This approach is entirely deterministic; we know exactly what the computer will “randomly” choose next. Even worse, there are major problems with this sequence of numbers. For one thing, there are significantly more instances of 0 than any other number. And did you notice that there are no 6s at all?

Now, we can improve things a bit if we create a better sequence. Here are a few ideas that are crucial for a decent sequence:

• One integer shouldn’t be considerably more prevalent than the other integers. Each integer should appear the same number of times or at least close to it. This attribute is known as uniformity.

• The numbers should be “mixed up.” If the sequence were 1, 2, 3, 4, and so on, it wouldn’t even seem random. Even though pseudorandom numbers are, by definition, not truly random, we could at least try to make them look random. We call this attribute lacking pattern. That is, the sequence should lack any discernible pattern.

• The sequence should have a lot more integers. The previous example has only 20 integers. Even if there’s no pattern within the 20 numbers themselves, there still ends up being a pattern in that the same 20 sequence numbers keep repeating themselves! After a while, a user of our software may begin to notice this pattern. But what if we had 100 integers? That would be a more difficult pattern to detect. The number of integers in the sequence before it begins again is called the period. A sequence with a long period is one that has many numbers in it, so it’ll take a while until the sequence starts over from the beginning again.

With this in mind, here’s a better-looking sequence:

This pattern contains 100 numbers, lacks pattern, and is uniform. Is it perfect? Far from it. But it’s a lot better than our first sequence.

As contrived as this all seems, this is pretty much how PRNGs work. Since a computer can’t generate a true random number, it fakes it. But it fakes it well enough to make the numbers seem random to the user.

Linear Congruential Generators

The concept of pseudorandom number generation is starting to take shape. But here’s a new monkey wrench: so far, we’ve only been dealing with random numbers from 0 through 9. But what if we want to generate a number that was, say, 7 digits long?

Indeed, Python’s random() method typically produces a number with a whole bunch of digits. Interestingly, the number generated is a float between 0 and 1. However, it has many digits beyond the decimal point. For example:

And herein lies the problem. If we want uniformity to the point where every possible float occurs at least once within our sequence, we’d need to prepopulate a sequence containing trillions of numbers. That’s a lot of memory to take up to enable a programming language to generate a random number.

Because of this, PRNGs don’t prepopulate a long sequence of numbers for the computer to cycle through. Instead, they use a clever trick to achieve a similar result. That is, the PRNG only has to remember the pseudorandom number it generated previously, and then it calculates the next number based on the previous number.

In other words, there is indeed a prepopulated sequence. But we don’t have to tell the computer the entire sequence up front. Instead, the computer figures out the next number based on the previous number.

Here’s a simplified example to demonstrate the basic concept.

Let’s make up a formula for generating random numbers between 0 and 210. It’ll go something like this:

1. Add 12549 to the previously generated random number.
2. Divide the result by 211.
3. Grab the remainder. This remainder will be the next number in our sequence.

Yes, this sounds like a calculation that I pulled out of a hat, and that’s because I did. But let’s see what happens.

If the previous number generated by the computer was 73, we’ll apply our calculation:

Therefore, 173 will be the next pseudorandom number.

Now, the next time the computer generates a number after this, the computer will grab the previous number (173) and apply the same calculation to generate a new pseudorandom number:

And so on.

This type of PRNG is called a Linear Congruential Generator, or LCG. The name isn’t terribly important, but you can impress your family and friends by saying that you spent your day creating your own Linear Congruential Generator.

There are a couple of other items I need to point out. You can’t pull any old LCG formula out of your hat, like I admittedly did, as it takes mathematical expertise to choose the “best” formula. For example, the number we’re dividing by (which in our example is 211) must be a prime number. You’ll read more about this soon.

There’s also another loose end to tie up. We now have a method to generate the next random number in our sequence. But how do we determine the first number?

For this, the programming language provides a starting value, which is called the seed. The seed can be any arbitrary number hardcoded straight into the programming language and used the first time the computer is asked to generate a random number. From then on, the sequence continues based on the LCG’s math formula. Many languages, including Python, use the current time to determine the seed.

A First Attempt at LCG

I whipped up the following code to serve as a basic LCG so that we can see what an LCG implementation looks like:

To run this code, I’ll call the generate_random_sequence function and pass in an arbitrary seed of 999:

This produces the following sequence:

Conveniently, this sequence contains all the numbers from 0 to 210 with each number occurring once. It turns out that this sequence has great uniformity and a period of 210.

However, this sequence is not so great when it comes to lacking pattern. Look at every pair of consecutive numbers: 44 and 144, 33 and 133, 22 and 122. That’s a pattern if I’ve ever seen one.

Short Circuit

Even without mathematical expertise, we can at least play with the numbers of the LCG formula to see if we can get a better pattern. If I change the formula to divide by 111, which is not a prime number, we get this result:

The first thing that jumps out at me is that this sequence has a short period.

In truth, this happens because when we get to the final number, 0, and apply the formula to it, we get:

We get 6, but you’ll notice that 6 is the first number in the sequence, so the sequence starts over from the beginning. That is, once the “current” generated number is 6, the next number must be 12 since that’s what our LCG formula dictates. We’re forced to return to the beginning of our sequence.

So, for an LCG to uniformly generate every number in a range of, say, 0 through 101, the LCG must generate each of those numbers once and only once before beginning the sequence all over again. The sequence will “short circuit” as soon as we generate a number we’ve already generated before, and we are forced to jump back to that point in the sequence.

Now, if you were to ask Python to generate an integer between 0 and 9 using random.randint(0, 9), it’s possible to get the same result twice in a row. But then the sequence would get locked into generating that same number over and over again. If, for example, the LCG formula says that the previous result of 4 produces another 4, then there’s no way to ever stop generating a 4!

The answer, though, is that when you execute random.randint(0, 9), under the hood, Python is generating a much longer number using random.random(), such as 0.5339767180649452, like you saw earlier. Python then does something along the lines of returning the final digit, like the 2 in our example.

However, when the computer generates the next number, it’s performing the LCG formula on 0.5339767180649452. This could produce a number like 0.11364654704325492, whose final digit also happens to be a 2. So it may appear as if you received the same number twice, but in truth, Python has generated a completely different number with many more digits. It’s just that both numbers happen to end with a 2.

This explanation might make sense for generating numbers between 0 and 9, but what about generating numbers between, say, 116 and 865? Indeed, the math that Python uses is slightly more complex than simply grabbing a final digit, but in any case, Python first generates a longer number and then converts it into a number in the range you’re looking for.

A Better LCG Formula

You saw that our previous LCG formula of (x + 12549) % 211 produced a sequence with a distinct pattern, which is problematic. Let’s tweak our formula again, this time using the numbers: (previous_number + 1223) % 227.

This time, we get:

This has all numbers from 0 through 226. We have good uniformity, a longish period, and a pattern that is more difficult to detect. Now, there is a pattern (can you find it?), but since it’s harder to see, our sequence has a greater appearance of randomness than before.

In the end, we managed to create a sequence of seemingly mixed-up numbers without having to store the entire sequence. Instead, we simply allow the LCG to do the work of computing the next number. The trick is to find the right formula, which takes mathematical expertise.

Luckily, mathematicians and computer scientists have developed a whole slew of PRNGs, some of which are LCGs and some that use other types of math. These PRNGs do the heavy lifting for us, and some have awesome names like Threefish, Philox, Mersenne Twister, and Blum Blum Shub. As of this writing, Python uses the Mersenne (pronounced mer-SEN) Twister, which is a type of LCG.

The Mersenne Twister is impressive, as it uniformly generates long numbers and also has a super-long period of about (2¹⁹⁹³⁷). That’s a massive load of numbers before the sequence wraps around to the beginning again.

Another important attribute of the Mersenne Twister is that a computer can execute its calculations quickly. Some LCGs are so involved that it may take the computer a stretch of time to compute the next number. While the Mersenne Twister is itself a complex formula, it’s one that a computer can execute with great speed. This is important, as you’ll see in the next section that an operation like shuffling an array has to generate many random numbers in succession. If generating a single random number is not fast, shuffling an entire array can become way too slow.