Math in… Random number generation

Most of the games we play involve an element of randomness. While there might be some strategy involved, but not knowing exactly how things will shake out in any given sitting is what makes games like poker, Yahtzee, Set, and Magic the Gathering infinitely replayable.

When making video games or other pieces of software that require randomness, how can you do it without cards to shuffle or dice to roll? Computers are deterministic machines, so anything we can code up cannot produce truly random results. If you want a TRNG (true random number generator), you need some source of external entropy.

True random number generators

One of my favorite examples of a TRNG is Lavarand, an array of six lava lamps designed by Silicon Graphics in 1996, images of which could be converted into numbers. Cloudflare has a 100-lamp tribute to this in their office that can similarly be used to generate random numbers:

Cloudflare’s “Wall of Entropy” (Photo: Dani Grant, via fastcompany.com)

While these are fun, most TRNGs rely on more mundane sources of external entropy. For example, when transmitting an electrical signal, what is received will differ slightly from what was sent. This noise is something we typically try to minimize, since it degrades audio, photos, or whatever information we are trying to send. However, since noise is statistically random, it can be used to generate random numbers. Since 2012, Intel has incorporated a TRNG based on thermal noise into its processors. (Much more compact than a wall of lava lamps!)

Pseudorandom number generators

The highest level security concerns in cryptography require true randomness so it is impossible to guess at a pattern generating certain numbers, but sometimes “seemingly random” is good enough. For those less demanding purposes, programmers use a PRNG (pseudorandom number generator). How can we get random-seeming numbers without a source of random data? The idea is to create a complicated function that can take a predictable input and garbles it into output that would seem random if you didn’t know the function.

Middle-square

It’s not a very good PRNG, but John von Neumann gave the example of the middle-square method, that is pretty easy to follow and gives a simple example of what we’re looking for.

Start with some number, square it, and then take the middle digits as your pseudorandom number. Starting with a \(4\)-digit seed \(1234\), we could square it and then add leading \(0\)’s until we get \(2 \cdot 4 = 8\) digits. Taking the middle \(4\) digits, we have generated \(5227\):

\[ 1234^{2} = 1522756 = 01\underline{5227}56 \]

We could do it again to get \(3215\)

\[ 5227^{2} = 27\underline{3215}29 \]

If we keep at it, always taking the middle four digits, we get

5227, 3215, 3362, 3030, 1809, 2724, 4201, 6484, 0422, 1780, 1684, 8358, 8561, 2907, 4506, 3040, 2416, 8370, 0569, 3237, 4781, 8579, 5992, 9040, 7216, 0706, 4984, 8402, 5936, 2360, 5696, 4444, 7491, 1150, 3225, 4006, 0480, 2304, 3084, 5110, 1121, 2566, 5843, 1406, 9768, 4138, 1230, 5129, 3066, 4003, 0240, 0576, 3317, 0024, 0005, 0000, 0000, …

It looks pretty random for awhile, but eventually ends up in a rut where it can only return \(0\). Ideally, a PRNG shouldn’t break down like this!

Park-Miller

A special case of the Lehmer RNG that was popularized by Stephen Park and Keith Miller takes a seed number, multiplies it by \(a = 48271\), and then takes the remainder of this product when divided by \(m = 2147483647\). Starting with seed \(1234\), we would get \(59566414\). We could then repeat this process to \(59566414\) to get \(1997250508\), and to \(1997250508\) to get \(148423250\). The numbers we get this way are

59566414, 1997250508, 148423250, 533254358, 982122076, 165739424, 1031150829, 305696493, 915275066, 1061641155, 1077924644, 1119207361, 1012415252, 11274513, 918654332, 973433069, 1645477339, 2006462927, 311985870, 1714598006, 1340592246, 1603571615, 2104855197, 1718907523, 1059373594, 1142153610, 549238879, 1624305994, 99200757, 1778691984, 697068957, 1441842151, 1364955298, 811416151, 2062270935, 1275846700, 860027034, 1358578057, 65777361, 1158162565, 223392764, 876719457, 1812161065, 1375375364, 1287248639, 1487210871, 925118478, 1619095820, 2001961949, 2088608826, …

Pretty random looking numbers, but it’s periodic. The middle-square method is also eventually periodic, just with a much shorter period. The 2,147,483,646th number that we generate will be 1234 and then the numbers above will repeat in exactly the same order! While that might seem like a big number, computers regularly run through billions of values. Also, while we listed out only the first so many numbers above, every number in the range 1-2,147,483,646 will come up exactly once on the way there, so this generator is like a die that must roll each value 2-6 before it can roll a 1 again — a notably nonrandom feature!

Xorshift

Many PRNGs use bit operations, since those are very computationally efficient. A relatively simple family of RNGs in this vein are the xorshift RNGs, created by George Marsaglia. Here’s how the 32-bit version works.

• Take a seed (we’ll again use 1234) and convert it to binary:

\begin{eqnarray} 1234 & = & 2^{10} + 2^{7} + 2^{6} + 2^{4} + 2^{1} \\ & = & 10011010010_2 \end{eqnarray}

\[ x = 10011010010_2 \]

• Add 13 zeros to the right end, shifting bits to the left by 13 places. Since we are working with 32 bits, if this new binary string has more than 32 digits, we’d lop them off from the left side until 32 remain, since they’ve been shifted “too far” left and out of memory. Ours doesn’t need this lopping, though:

\[ x’ = 100110100100000000000000_2 \]

• Take the XOR (\(\wedge\)) of our seed \(x\) with this new value \(x’\). You can think of this as lining the two binary numbers up and creates a new binary number with a \(0\) in positions where their digits are the same and a \(1\) where they are different. In our case, there is never a \(1\) above a \(1\), so it just looks like addition:

\[ \begin{matrix} & 000000000000010011010010_2 \\ \wedge & \underline{100110100100000000000000_2} \\ & 100110100100010011010010_2 \end{matrix} \]

• Call this new value \(y = 100110100100010011010010_2\) and make \(y’\) by shifting its bits right 17 places, lopping off the rightmost 17 digits since they’ve been shifted out of memory:

\[ y’ = 10011010_2\]

• XOR \(y\) and \(y’\):

\[ \begin{matrix} & 100110100100010011010010_2 \\ \wedge & \underline{000000000000000010011010_2} \\ & 100110100100010010011111_2 \end{matrix} \]

• Call this value \( z = 100110100100010010011111_2 \) and make \(z’\) by shifting its bits left \(5\) places. We’d again lop off from the left if it is over 32 digits long, but it isn’t:

\[ z’ = 10011010010001001001111100000_2 \]

• XOR \(z\) and \(z’\), this time noting there are some \(1\)’s above \(1\)’s:

\[ \begin{matrix} & 00000100110100100010010011111_2 \\ \wedge & \underline{10011010010001001001111100000_2} \\ & 10011110100101101011101111111_2 \end{matrix} \]

• Then we convert the result back to decimal:

\[ 10011110100101101011101111111_2 = 332584831\]

It seems a little complicated, but it’s really just the same pair of steps done three times in a row: shift the bits in a number either left or right and then XOR that number with its bit-shifted self. After the third time, we have our pseudorandom number \(332584831\). And we could apply this iteratively to the outputs to get more pseudorandom values:

332584831, 1855942593, 4018585650, 3348358578, 3751476256, 2211002831, 987888983, 2888360370, 3015822877, 3393669276, 1238368246, 1881012526, 674466034, 2089904356, 1614136418, 3481595902, 488365731, 3208525124, 1262991471, 889900810, 4053571231, 178757688, 716911208, 3526661747, 1604327374, 4133934370, 3029527331, 3609789656, 33398561, 4045742989, 4290874823, 22566299, 1988967854, 4129960818, 3099672912, 2374643077, 3479689880, 2997670082, 1042552728, 641628051, 4047510869, 2947694624, 292572315, 75972010, 2238941779, 1930140079, 133255088, 4008464083, 2180363336, 3639169334, …

These numbers will again be periodic, but there are ways to tweak it to make periodicity less apparent.

Chrome and many other web browsers have been using xorshift128+ since about 2015. That tweak on the classic xorshift takes two 64-bit numbers, does some bit-shifts and XORs to each them separately, like we did above, and then adds the results to return a pseudorandom 64-bit number. The results pass a lot of basic randomness tests, but there is still a lot of hemming and hawing in the RNG community about whether they’re random-seeming enough!

What is “random-seeming enough,” though? Once you have a candidate for a PRNG, you can run a variety of statistical tests on its output to check whether they behave randomly. TestU01 and PractRand are a couple of suites that researchers use to test potential PRNGs. They check for things like periodicity, linearity, irregularities in the distribution (e.g., way more odd numbers than even numbers), unexpected geometric structures, and more. Of course, passing these tests might just mean the PRNG is only bad in ways we haven’t thought to detect yet!

Can you think of any interesting ways to make seemingly random numbers?