Roll your own random number generator
Or, how to manually generate series of random integers with dice
Random numbers have many practical uses—their unpredictability makes lotteries fair, makes scientific experiments useful, makes statistical simulations reliable, makes cryptography secure, and makes board games fun and engaging. While we often depend on computers to generate random numbers, we will here explore how to manually operate a random number generator (RNG) using dice.
Our RNG, which we assign the code name Rollo (after the viking), will provide us with series of integers chosen uniformly at random from any ranges we request.
In a previous story, we showed how to use one type of die to simulate any other type of die—real or imagined. The RNG we shall construct here is an extension of the approach described in that story. Thus, we start with a brief summary.
Expand, extract, reject
By combining three procedures, which we here refer to as expansion, extraction, and rejection, we can simulate any type of die from another.
The first, expansion, allows us to expand the result of one die roll with the result of another. Repeating this procedure allows us to simulate the roll of an arbitrarily large die.
The following figure illustrates how we would expand the result of a four-sided die (D4) with the result of a six-sided die (D6) to simulate the result of a twenty-four-sided die (D24).
We could then continue to roll a D6 to expand this result to simulate a D144, a D864, and so forth.
When we have a result from a larger die than we need, we may attempt extraction—to output a result simulating the requested die. However, we only do this if we can guarantee the output to be fair. To check this, we need to figure out the largest multiple of the requested die that fits our current, larger die. The largest multiple marks the upper limit of the extraction range—we can only extract a fair result if our current result is within this range. Otherwise, the result is within the rejection range. Then, we reject to output anything and keep rolling dice until we can make a new extraction attempt. In addition, we attempt to preserve any unused randomness when we extract or reject.
The following figure illustrates how we would attempt to extract the result of a D9 from a D24.
The largest multiple of 9 that fits 24 is 18. Then, if the result of the D24 is in the extraction range 1–18, we can consider this as the combined result of a D9 and a D2. We can then extract and output the result of the D9. We keep the result of the leftover D2 for later use.
Otherwise, if the result of the D24 is in the rejection range 19–24, we cannot extract any fair result of a D9. However, we may consider this as a result of a D6, and keep this result for later use.
Setting up and operating the RNG
The output of our RNG will be a sequence of simulated die rolls, from die types we request in advance. We will use an imaginary die to keep track of the current state of our RNG; we refer to this as the state die. This is the setup of the RNG:
1. Setup. Before feeding the RNG with any input, we specify the sequence of requested die rolls the RNG will generate and what source to use for random input. Then we set the state die to a D1 with a current result of 1.
The basic operations of the RNG then consists of the three procedures described above:
2. Expansion. Whenever the state die is too small to cover the range of the next requested output, we roll a physical die and use its result to expand the state die. We repeat this process until the state die covers a large enough range. Then, we compute the largest multiple to determine if the current result is in the rejection range or the extraction range; the largest multiple marks the upper limit of the extraction range. The computations used in the expansion procedure are:
3. Rejection. If the state die is large enough to cover the range of the next requested output, but the current result is in the rejection range, we reduce the state die by subtracting the largest multiple from both its result and its number of sides. Then, we go back to expansion. The computations of the rejection procedure are:
4. Extraction. If the state die is large enough to cover the range of the next requested output, and the current result is in the extraction range, we extract and output the result of the next requested output. Then, the leftover die result becomes the new state die. If there are more requested outputs, we keep operating the RNG until all outputs are generated. The computations of the extraction procedure are:
A worked example
As an example, say that we want our RNG to select a random card from a standard 52-card deck. First, we could request a random integer in the range 1–4 to choose suit (clubs, diamonds, hearts, and spades). Then we would request a random integer in the range 1–13 to choose rank (ace, 2, 3 … 10, knight, queen, king). To do so, we would first request our RNG to simulate rolling a D4, then a D13.
To operate our RNG, we will here use a D6 die, a pen and a piece of paper. On the paper, we use four columns to keep track of all operations: Operation type, die input, state die, and die output. This also makes the process transparent and easy to audit.
We start by listing D6 as the input source, set the state die to D1 with result 1, and list the requested die output sequence as D4, D13.
Then, we start to feed the RNG with random input. We roll the D6, get a result of 6, and expand the RNG state.
The state (D6) is now large enough to attempt to extract the first output (D4). The largest multiple is 4, which brings the current state result of 6 in the rejection range 5–6. We then reject any output and reduce the state by subtracting the largest multiple. The state is now a D2 with a result of 2.
Then, we roll our D6 again, and get a result of 3. This expands the state to a D12 with a result of 9 (computed as (2 − 1) × 6 + 3).
This result is in the extraction range 1–12. The largest multiple of 4 that fits in (9 − 1) is 8. We subtract 8 from 9 and get an output result of 1 for the D4.
Then we compute the integer quotient from dividing (9 − 1) by 4 and add 1 to get a leftover die result of 3. The leftover die is a D3 (computed from dividing 12 by 4).
There are quite a few numbers to keep straight when extracting, so we may check that our D3 and D4 actually combine to produce the state result we extracted from: (3 − 1) × 4 + 1 = 9.
Then, we proceed to generate the D13. We roll a 4, this puts the result of the state die in the rejection range 14–18. Then we roll a 3, which allows us to extract a D13 with a result of 2.
In this example, we needed 4 rolls of a D6 to simulate a D4 and a D13. The randomly selected card is the two of clubs.
Other inputs and outputs
Our RNG could use any type of die as input, such as a D4, D8, D10, or D20. We could also use other types of input sources if they provide integers uniformly at random, and then map them to the corresponding die type. For example, a series of binary octets (from the range 0–255) could be considered results from a D256−1 and translated to results from a D256 by adding 1.
The RNG can be used for a variety of random outputs, provided that requested outcomes can be decided by imaginary dice. A few examples:
- We have already shown how to map playing cards to a D4 and a D13
- We could choose integers from any range, such as 7–11 by rolling a D5 and adding 6 (D5+6)
- We could choose a rational number in the range 0.000–1.000 uniformly at random by rolling a D1001−1, and then divide by 1000.
- We could produce bits by simulating a series of D2 and subtract 1.
Caution
If this RNG is used for any important purpose, like determining winners of games or lotteries, it is important that all choices are made before operating the RNG. This means that the sequence of requested outputs should always be specified before feeding the RNG with any input, as it is possible to predict likely outputs during operation of the RNG.
Likewise, the source of random input should not be allowed to be chosen during operation. Whenever new output requests are made or there are any changes in the RNG setup, the RNG should be reset by running the setup procedure.
So, is this RNG any good?
For specific purposes, like generating series of random bits, it is possible to construct dice-operated RNGs with far better performance than our Rollo. When using a D6, always rolling it twice (expanding the state to a D36) will generate bits at a far higher rate per roll than using the standard procedure above.
However, as a general-purpose flexible manual RNG, our Rollo works well. It attempts to provide output as soon as its state has enough randomness, it attempts to preserve as much randomness as possible, it is fairly easy to compute by hand, and the process is transparent and easy to audit.
So, do you feel like spending som quality time with a die, generating series of random integers? Rollo, cast your die.
Appendix
R simulation generating a D4 and D13 from a D6 ten million times
Not convinced that the RNG produces fair output? Here is a simulation in R for the example with the D4 and the D13 selecting a random card (corresponding to a D52).
Rollo <- function(source_die, requests) {
state_result <- 1
state_sides <- 1
position <- 1
results <- c()
while (position <= length(requests)) {
requested_sides <- requests[[position]]
while (state_sides < requested_sides) {
# expansion
roll <- source_die()
state_result <- (state_result - 1) * roll$sides +
roll$result
state_sides <- state_sides * roll$sides
}
largest_multiple <- floor(state_sides / requested_sides) *
requested_sides
if (state_result > largest_multiple) {
# rejection
state_result <- state_result - largest_multiple
state_sides <- state_sides - largest_multiple
} else{
# extraction
quotient <- floor((state_result - 1) / requested_sides)
results[[position]] <-
state_result - requested_sides * quotient
state_result <- quotient + 1
state_sides <- largest_multiple / requested_sides
position = position + 1
}
}
results
}D6 <- function() {
list(result = sample(1:6, 1),
sides = 6)
}freq <- list(
D4 = rep(0, 4),
D13 = rep(0, 13),
D52 = rep(0, 52)
)test <- function(iterations) {
for (i in 1:iterations) {
result <- Rollo(D6, c(4, 13))
r <- result[[1]]
freq$D4[[r]] <<- freq$D4[[r]] + 1
r <- result[[2]]
freq$D13[[r]] <<- freq$D13[[r]] + 1
r <- (result[[1]] - 1) * 13 + result[[2]]
freq$D52[[r]] <<- freq$D52[[r]] + 1
}
}set.seed(413)
options(digits = 3)
test(1e7)freq$D4 / sum(freq$D4)
# [1] 0.25 0.25 0.25 0.25freq$D13 / sum(freq$D13)
# [1] 0.0769 0.0770 0.0768 0.0768 0.0770 0.0769 0.0769 0.0770
# [9] 0.0769 0.0770 0.0769 0.0769 0.0770freq$D52 / sum(freq$D52)
# [1] 0.0192 0.0193 0.0192 0.0191 0.0193 0.0193 0.0192 0.0193
# [9] 0.0192 0.0192 0.0192 0.0192 0.0192 0.0192 0.0193 0.0192
#[17] 0.0192 0.0192 0.0193 0.0192 0.0192 0.0192 0.0192 0.0192
#[25] 0.0192 0.0192 0.0193 0.0193 0.0192 0.0193 0.0192 0.0192
#[33] 0.0193 0.0193 0.0193 0.0192 0.0192 0.0192 0.0193 0.0192
#[41] 0.0192 0.0192 0.0192 0.0192 0.0192 0.0192 0.0192 0.0192
#[49] 0.0192 0.0193 0.0192 0.0192
