In previous posts we have talked about dice mechanics, dice rolling, and a lot about adding dice rolling support for D3, World of Darkness, and specialc ases like initiative rolls in Pathfinder. In none of these posts did we actually explain how RPGpad rolls the dice you request. The reason for this is that the actual details are a very technical topic, which boils down to a lot of math and trickery with binary numbers — not something that makes for a good post.
Computers are known for doing the same thing over and over again very fast. And if you give them the same inputs, they’ll quickly come up with the same outputs, time and time again: they do not randomly do something else.
So, how do computers generate random numbers?
Well… They don’t, technically.
The random numbers you get from a computer are called “pseudo-random” — they can come close to real randomness. Unfortunately, real randomness is very hard to get and involves a lot of dedicated hardware. So, instead computers use math to produce numbers that come very close to being random. These numbers are called pseudo-random numbers and the are generated with a — you’ll never guess the name — a pseudo-random number generator. To show you how this works, I’ve build my own tiny pseudo-random number generator.
Try and see if you can guess the next number to come along when you press “New number”!
If you play around with it long anough, you’ll start to spot a pattern. And once you do that, you can predict the next number. That’s why it is called a pseudo-random number generator. Our tiny pseudo-random number generator isn’t all that good at generating numbers, but it serves the purpose of being clear on how it works.
To keep the tiny generator tiny, we want it to do the following:
- Produce a new pseudo-random number every time we press the button,
- produce small numbers from 0 to 8 inclusive, so any number from 0 up to and including 8 is fair game.
The two things we want are directly related to each other, as you’ll see!
First off, we need to come up with something that will produce numbers that seem random. This can become somewhat tricky, since one of the big things in mathematics is that the results do not change if you do the same calculation with the same input numbers.
2 + 2 will always be
4, no matter how often you do it.
So, we’ll need a way to vary the input numbers, or our generator will just go:
4,… until the end of times.
And here comes the really sneaky part of our tiny generator: if we just assume it works, that means that we can get pseudo-random numbers, and then we can use the current random number from our generator as the input for the next number! Brilliant!
So let’s try that. We’ll call the current random number
Xn, and we we’ll call the new number we are generating
Xn+1 — so
X1 will be the first random number,
X2, the second, and so forth.
Now, we need to think of something that will produce a good new number. So, here goes the first attempt:
Xn+1 = Xn
Ah… We hit the first problem straight away. We need some starting value
X0, the seed number from which all other numbers will be produced. Let’s just say that
X0 = 4 for now. With that done, let’s try it:
Xn+1 = Xn
Nope. That’s obviously just the
4,… generator, since it does not do anything with the input number. We’ll need to do something at least.
For our second attempt, let’s just add a number every time so that we have some change every time we make a new number:
Xn+1 = Xn + 2
That does not work out as well as hoped: the numbers just keep getting bigger and bigger without anything to get them back to something more managable. There is a good way to deal with it, but we’ll have to take a bit of a detour to first find a way to keep the numbers small:
Modulo — we want our tiny generator to produces numbers from 0 to 8. So we need a way to make sure that we will not get larger or smaller numbers. The easiest way to do that is to do whatever we want to do, get a big number, and then keep subtracting 9 from it until it is between 0 and 8. For example, let's say we have the sum
4 + 7 = 11
the result is larger than 8 so we subtract 9:
11 - 9 = 2
We can do this over and over, if necessary. Which would lead us down a rabbit-hole of subtractions:
7 * 7 = 49
which is clearly above 8, so we subtract 9 from it until it isn't:
49 - 9 - 9 - 9 - 9 - 9 = 4
Since this is getting unwieldy to write let's write this 'keep subtracting nines part' with a shorthand:
7 * 7 mod 9 = 4
mod 9 part says that we want to keep the number between 0 and 8, and allows us to omit the many
- 9 we would need for even larger numbers — we use "mod" because it is short for "modulo" which is what this operation is called in mathematics. Another way to look at
mod 9 is to say that it is the remainder after division by 9.
Now, we can use any number, and still stay between 0 and 8:
12 * 34 + 56 mod 9 = 5
If you want to check that for yourself, just keep subtracting nines. You'll be busy for a while though, as you'll be doing it 51 times, since
12 * 34 + 46 = 51 * 9 + 5. Being able to keep numbers small makes the next part easier.
Now that we know how to keep the numbers small, for our third attempt, we’ll also use
mod 9 to make sure that we do not get ever-growing numbers. Let’s see how this turns out:
Xn+1 = Xn + 2 mod 9
This is going somewhere, but it is still a bit on the predictable side.
For our fourth attempt let’s make larger jumps by introducing some multiplication. By multiplying the input number first we’ll jump through the available numbers because we’ll be getting much bigger numbers, but we keep subtracting 9 from them a few times, so it is much less predictable where we’ll end up:
Xn+1 = 4 * Xn + 2 mod 9
After hitting the ‘New number’ button a few times you might recognize a pattern, but this is jumping around nicely. The first generator you used at the top of the post is actually using this formula, but it adds
1 instead of
2, which leads to a different pattern! We could keep on tinkering with different numbers and more complex calculation, but this blog post is on the long side already, so I’ll wrap it up here.
I want to point out that the tiny pseudo-random number generator in this post isn’t very good for generating numbers. The tiny pseudo-random number generator we built up here is known as a linear congruential generator. For the dice roller in RPGpad we use a much better generator called a Mersenne Twister, which been battle-tested for decades now and is in use in a lot of software that needs pseudo-random numbers.
As always, we have this week’s changelog prepared for you if you want to have a look at the changes to RPGpad. And if you want to talk more about randomness, have an idea for a feature, have an issue with RPGpad, or just want to chat, open a thread in the community forums!
As a bonus, here is the tiny generator again, this time with adjustable parameters for all numbers in the calculation:
Xn+1 = a * Xn + c mod m