How do computers generate random numbers?
Random variables are so beautiful — they find applications almost everywhere. Thanks to some well-analyzed distributions, random numbers make real-world analysis quite easier. Not only are they useful for convoluted stochastic systems analysis, but random numbers also find their application in things as simple as emulating a roll of dice in a ludo game. It is hardly surprising that almost all major programming features support random numbers.
#include <iostream>#include<cstdlib>using namespace std;int main() {int x = rand() % 100; //rand() is a primitive function in C++ to generate random numberscout << x;return 0;}
But have you ever wondered what the process behind random number generation is? Random number generation follows certain algorithms as well, though (spoiler alert) they can't generate absolutely random numbers.
Pseudo-random number generation
This limitation leads to the term pseudo-random number generation (referred to as PRNG afterward).
Middle-square method
John von Neumann proposed the middle-square method in 1946. It’s based on a 13th-century technique in which we take a number, square it, and then take the middle-n numbers of the square as the output. The output then serves as the seed for the following random number's generation. It was prone to error due to repeated generations after some time. von Neumann wasn’t unaware of this (general PRNG) flaw and cautioned in his famous quip:
“Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.” (1951)
Progress
The middle-square was followed by better algorithms like the Lehmer generator, LCG, MixMax, Mersenne Twister, and many others. The table below outlines some of the most influential PRNGs in the last quarter century.
Title | Year | Notes |
Mersenne Twister | 1998 | Arguably the most commonly used PRNG |
Xorshift | 2003 | Quite fast PRNG |
Threefry | 2011 | Suitable for GPU implementation. Used in JAX |
Xoroshiro 128+ | 2018 | One of the fastest generators on 64-bit CPUs |
Some modern languages like Python and R use Mersenne Twister as their default PRNG.
Making a PRNG
While the PRNGs are a topic broad enough to have a course of their own, we can still get the intuition behind them by making a naïve PRNG ourselves.
To make a PRNG, we need a separate class. It should have:
PRNG()- A function that would return the generated number.Seed - Seed is a pretty useful concept that allows us to generate the PRs (not that PR) in a replicable manner.
#include <iostream>#include <array>class RandomGenerator {static int seed;public:RandomGenerator(int s) {seed = s;}int PRNG() {int x = 1069;int y = 2423;int z = ((x * seed + y) % y) + ((x * seed + y) / y);seed++;return z;}};int RandomGenerator::seed = 0;int main(){RandomGenerator rng(3);for (int i = 0; i < 100; i++) {std::cout << rng.PRNG() << std::endl;}return 0;}
In the code above, PRNG() just took two random prime numbers (why: that’s another story and will be explained some other day), made a silly combination of them, and returned it. The constructor of the class (RandomGenerator()) is setting the seed.
Bonus - C#
If you are into C# or interested in learning it, there is a C# code in the other tab as well. It's more or less the same except for line 32, which is arguably a stroke of genius. It takes the first 100 natural numbers, which is a good enough sample size given we are operating only on integers and seeds our PRNG accordingly.
Note: Please feel free to change the seed value in line 31 to have different random outcomes.
This PRNG is quite limited as it doesn’t provide us control over range, but it returns pretty good random numbers (never forget von Neumann’s quote above).
Free Resources
- undefined by undefined
