Pseudorandom Number Generation
Most of us don’t often think about how random numbers are generated or even why they’re needed. Believe it or not, random numbers are all around us. They are crucial to various facets of computing such as games, cryptography, running simulations, statistical sampling, and more. Because of the importance of many of these applications, random number generation has been studied a great deal in computer science.
You may ask, how are random numbers generated by computers? Computers are inherently deterministic machines; you make a mathematical function, give it some inputs, and it gives an output. For the same set of inputs, the output is always identical. This fact is sort of contrary in nature to randomness.
The truth is computers cannot really create true random numbers. Instead, they produce pseudorandom numbers (The prefix pseudo comes from the Greek word for false). In producing random numbers, we use mathematical formulas to produce sequences of numbers that act kind of random. Some of these generators are actually quite good; a sequence of randomish numbers that repeats itself after a few trillion bits isn’t so bad! I will explain how random numbers are generated by computers and then show you my own pseudorandom number generator implemented in Java.
Let’s begin with a trivial form of random number generation proposed in 1946 by John von Neumann. It is called the Middle Square Method. Let’s say we want to generate random numbers from 0 to 10000. First, take any 4-digit number. It is called the seed. Let’s choose 5555. We square the seed producing 30858025. The middle 4 digits, 8580, become our result (and also our seed). To then generate another random number, we take the seed, 8580, and square it to obtain 73616400. The resultant random number is 6164.
This algorithm is really neat in the sense that pretty much anyone anywhere can generate pseudorandom numbers with a pencil and paper or the calculator app on their smartphone. However, as you might imagine, it has a couple flaws. What happens if we somehow get to a seed of 0000? That’s right, the random number generator will output “0000” forever which is obviously a highly undesirable behavior. It’s actually a behavior that more legitimate PRNGs face. Such seeds are called “bad seeds” because once you reach them, the generator becomes stuck in a short sequence of repeating numbers. You may think an easy solution to the “0000” bad seed in the Middle Square Random Method would be to just add a fixed number before you square it. For example, do \((Seed + 71)^2\) instead of just \((Seed)^2\). You’d be correct in thinking that! Adding an increment helps prevent “bad seeds” from being quite so bad.
Now let’s get into the actual algorithm I used for my PRNG. First, let me be clear; this algorithm doesn’t produce the best random numbers around. On the other hand though, it’s extremely fast, it’s used extensively today, and it produces random numbers that are “good enough” for many applications. It is called the Linear Congruential Method. It goes like this: take the seed and multiply it by a really large number. Since computers use modular arithmetic, if the number is too large after the multiplication (it probably will be), it will “wrap around.” Normally when generating random numbers, this “wrap around” happens several hundred times. It’s sort of like spinning a wheel; it’s somewhat unpredictable where it will stop. After the multiplication, we add an “increment” to help prevent bad seeds as explained previously. That’s all there is too it! I also added some extension methods to make the random number generator more usable in actual applications.
Here is the stripped-down version of the code of my random number generator along with a call in the main method that will generate 10 random numbers from 1 to 100.
Let’s do a quick step-though of what exactly happens when the PRNG is seeded and then a number from 1 to 100 is generated.
- The constructor is called.
7744144276301gives us a start seed of
- The seed
4094473531130* the multiplier 1103515245 overflows exactly 245 times. After all the overflows, we get
- We add our increment of
0xbeef(48879) to obtain the new seed,
nextInt(int n)method is called. After making an argument check, it calls
nextFloattakes the first 29 bits of the seed. Our seed in binary is
1111000000110011110100010100000000000100111110011010101101100001, so the first 29 bits are
11110000001100111101000101000. As an integer that’s
503740968divided by the max 29-bit float value of
5.36871012E8gives us the return value of
nextFloat’s return value of
0.9382904and multiplies it by
n=100to give us
93.82904which is converted to an integer giving us
- We add 1 to get the result of
Be sure to check back later for a post on the topic of running tests for randomness on random number generators!
Edit: Link to my article on statistical tests for random number generators
Link to my random number generator (you’re free to use or modify it as you like!)