# 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 30__8580__25. 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 73__6164__00. 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.
`System.nanoTime()`

returns`522952139754313`

.`522952139754313`

modulo`7744144276301`

gives us a start seed of`4094473531130`

.- The seed
`4094473531130`

* the multiplier 1103515245 overflows exactly 245 times. After all the overflows, we get`-1138336207903069070`

. - We add our increment of
`0xbeef`

(48879) to obtain the new seed,`-1138336207903020191`

. - The
`nextInt(int n)`

method is called. After making an argument check, it calls`nextFloat`

. `nextFloat`

takes 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`503740968`

.`503740968`

divided by the max 29-bit float value of`5.36871012E8`

gives us the return value of`0.9382904`

`nextInt`

takes`nextFloat`

’s return value of`0.9382904`

and multiplies it by`n=100`

to give us`93.82904`

which is converted to an integer giving us`93`

.- We add 1 to get the result of
`94`

.

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!)