(actually “pseudo-random number generators” but we’ll get to that later)
Attempting to write for a general audience which is why I’m attempting to use simple explanations and focus on explanations rather than code.
How do they work
- prepare a bunch of bits (a seed), and from these bits, create the initial state of the generator
- modify current state
- given current state, produce a number from it
Example 1: MINSTD
Step 1: The state is a single 32-bit unsigned integral number variable. We don’t know how to create a seed yet, so let’s pick a number 23455264 as a seed.
state = 23455264Step 2: Calculate the new state using the equation
(a*state + c) % mMINSTD in particular uses a = 48271, c = 0, m = 2147483647
state = (48271 * state) % 2147483647Step 3: use the new state directly as the output number
output = newstate
output = 485166575Done: this generator provides numbers in range from 0 to 2147483647 (exclusive, so it will generate every non-negative smaller than 2147483647). Want another number? Go through steps 2-3 again.
Example 2: Doom (1993) pseudo-random number generator
Step 1: prepare an array of 256 (hopefully) random numbers. The array is not part of the current state, as it is not modified during step 2.
rndtable = [ 0, 8, 109, 220, 222, 241, 149, 107, 75, 248, 254, 140, 16, 66,
# the full table is too long
120, 163, 236, 249
](if you want to see the full table, check out this link)
Also prepare an integral number variable. This is the state of the generator.
state = 0Step 2: Increase the number by 1. If the number goes beyond what is an acceptable range of indexing the array, set it to the index of the first element.
state = (state + 1) % 256Step 3: use the state to index the array.
output = rndtable[state]
output = 8Done: this generator provides numbers in range from 0 to 255 (inclusive)
Tricks and Traps
Generating a number from range 0 to N*N (exclusive) when your generator only provides numbers from range 0 to N (exclusive)
Generate two numbers using your generator
high = gen() # let’s say N = 10
low = gen()Multiply one of the numbers by N and add the second number
x = high * N + lowBecause “N” (10) is bigger than any possible value of “low” (0, 1, 2, …, 9), no two different generations of “high” and “low” will result in same “x”. The lowest possible value of x is 0 for high = 0 and low = 0, and highest is 99 for high = 9 and low = 9.
Generating a number from range 0 to H (exclusive) using a generator that provides numbers from range 0 to N (exclusive), and H is less than N
Let’s say N = 10 and H = 4.
Step 1: find the biggest possible integral number divisible by H which is smaller than N. Let’s call that number S.
Here S = 8 as 2*H = 8, but 3*H = 12, which is already bigger than 10.
Step 2: generate a number. If the number is not smaller than S, throw it away and generate another one until the generator will get you a number smaller than S
while True:
x = gen()
if x < S:
breakStep 3: Put the generated number into one of H buckets by using the modulo operation. Let this will be the resulting number.
b = x % HGenerated number: 0 1 2 3 4 5 6 7 8 9
Resulting bucket: 0 1 2 3 0 1 2 3 0 1
As you can see, if we were to not apply the step 2, before doing step 3, values 0 and 1 would be 50% more likely to be generated than values 2 and 3. Good thing we discarded 8s and 9s before doing that.
Pseudorandomness
We’re calling these numbers pseudorandom because we used a fairly simple step-by-step procedure to generate them, but also it is fairly difficult to say what would true randomness be.
We will never know if the devil creature will say something else than nine.
The two examples listed above were very simple pseudo-random number generators (PRNGs), but we have PRNGs which are good enough to generate numbers which must be unpredictable enough to secure your connection to your online bank. We call these cryptographically secure pseudo-random number generators. Explaining on how to use them will come in another post.
Picking a seed
We deliberately avoided explaining how to pick a seed for step 1 in both of these examples. Doom (1993) always picks 0 at the start of the level, but we have to keep in mind that using the same seed will result in the same sequence, which is why if we want to have different sequences, we will have to pick different seeds.
Two most common ways are using the current time, which is extremely predictable (everyone knows the current time), but good enough for quite a lot of programs. The alternative is using a better generator to seed our generator.
Picking a specific seed
The flip side of the fact that using the same seed results in the same sequence is that we can deliberately pick a seed to create the same sequence every time.
If you have ever played Minecraft or Factorio and saved a specific world seed to share with your friends, you know what I’m talking about.
Because Doom (1993) always uses the same seed and also has two separate generator states, one specifically for game logic and other for everything else, it can record your playthrough by recording your inputs and then replay it by simulating a player that rather than taking inputs from your keyboard or mouse, it takes input from the replay file.