# Aproximating 100 by 6

You're a fan of pen & paper RPGs and have finally arranged a new playing group, recruited amongst your friends from the mathematical faculty.

As a GameMaster (GM) you've assumed that all your players will be fully equipped with the necessary dice showing 4-sides (d4), 6-sides (d6), 8-sides (d8) 10-sides (d10), 12-sides (d12) and 20-sdies (d20). So your disappointment is great, when you show up for the game and all they have brought with them was a near-infinite amount of ordinary, six-sided dice.

While you luckily didn't need to have 'all' dice in your set, the RPG system you want to play with is based on d100 ( usually realized by using two d10 ), and you have to find a way of using (any number) of d6 and any rule you can think of, to realized a value range 0-99 (or 0 to 99).

One mathematician suggests:

We simply roll twenty of our d6, sum the rolls and subtract 20, that gives us the range (20;120)-20 = (0;100), and we consider both the 0 and the 100 to be 100.

This works, but chances for the various values are rather far from being an equal "fair" distribution, so soon the punch of players start a heated discussion on how they can 'best' achieve a fair distribution. They agree on the following metric:

"Ideally, each value has a chance of 0.01, so the best rule is the one which minimizes $$\Sigma(( P_i - 0.01 )^2)$$" - it does not matter how many (finite) rolls of d6 are used.

Under these conditions, what is the "fairest" method of getting to a range 0..99 (or 1..100) just using six-sided dice?

## Notes:

• I do not know a "best" solution for this (yet)
• the 'algorithm' has to produce any value of the D100 range
• The "fairest" algorithm wins. Only if two algorithms are equally fair, the one with less dice rolls wins.
• the 'algorithm' can consist of any mathematical rule which you can think of, but it must be reasonably "doable" by a punch of mathematicians with nothing but pen & paper (and d6)
• Any finite number of d6 ( or rolls thereof) may be used in the 'algorithm'

Note, that the last rule exclude all algorithms which do not guarantee that a result is reached in a finite number of rolls. (In particular, you can not re-roll until a certain value is rolled. You may reroll 1e106 times though.)

• ...this puzzle question is not fully fictive... – BmyGuest Dec 13 '15 at 18:40
• Are we allowed to reroll based on values of dice? Cause that would make this question trivial. You'd roll a d5 (d6 where 6s are rerolled) to divide into 20s, another to divide into 4s, then a d4 (d6 where you reroll 5+) to get your number. – DrunkWolf Dec 13 '15 at 19:15
• "near-infinite amount of ordinary, six-sided dice" - Well, your friends obviously expected to play Shadowrun. – Sleafar Dec 13 '15 at 19:53
• There does not exist a "best" solution to this problem. You can't get an error of zero, though you can get as close as you want to zero. – Mike Earnest Dec 14 '15 at 0:21
• I take exception to the notion that the mathematician would not immediately realize that 20d6-20 is not even close to a d100. – Todd Wilcox Dec 14 '15 at 18:30

As xnor points out in his answer, this question is basically asking for the way to most evenly distribute $6^n$ results among $100$ bins, and gives a very brief description of the solution. I'll go into a bit more detail here. If you're not interested in the proofs, skip to section 2.3

## Summary

In order to construct a "best" algorithm for converting rolls of one die into another, there are two types of optimality to consider:

• Minimum "score." BmyGuest's metric: $$\sum_i ( p_i - 1/100 )^2$$ is basically the chi-squared statistic for goodness-of-fit, between the distribution resulting from the algorithm and a uniform distribution. I'll call the metric applied to a particular algorithm that algorithm's score.
• Minimum number of rolls. I'll consider only the expected number of rolls for an algorithm.

Note I'll be diverging a from typical RPG terminology: when I refer to $\mathsf{3d6}$, for example, I mean that you should roll three six-sided dice without adding them, keeping track of the order the dice were rolled in (usually the dice are treated as indistinguishable from each other, i.e. rolled all at once). This is important because, as you noted, the results in a traditional roll are not equiprobable.

I also consider a $\mathsf{d}n$ to be numbered from $0$ to $n-1$, to make some of the math a little easier. If you're following my algorithms with real dice, just map $n\to 0$ for the input and vice-versa for the output.

# 1 Optimal Scoring Algorithms

In the general case, we want to map $m$ "results" into $n$ "bins." (In the original case, we have $m=6^k$, $n=100$.) Consider an algorithm that maps $r_i$ results to bin $i$.

The probability of landing in bin $i$ is $r_i/m$, so the score is:

$$\sum_{i=0}^{n-1}\left(\frac{r_i}{m} - \frac{1}{n}\right)^2$$

## 1.1 Distribution of an Optimal Algorithm

Since the score is a sum of independent terms we can easily isolate the effect of changing a pair of elements of the solution, $(r_i,r_j)$. Let's decrease $r_i$ by $1$ and increase $r_j$ by $1$, and see under what conditions the score decreases:

\begin{align} \left(\frac{r_i}{m} - \frac{1}{n}\right)^2 + \left(\frac{r_j}{m} - \frac{1}{n}\right)^2 &> \left(\frac{r_i-1}{m} - \frac{1}{n}\right)^2 + \left(\frac{r_j+1}{m} - \frac{1}{n}\right)^2 \\ \frac{r_i^2 + r_j^2}{m^2} - 2\frac{r_i + r_j}{m n} + \frac{2}{n^2} &> \frac{r_i^2 + r_j^2 - 2(r_i - r_j) + 2}{m^2} - 2\frac{r_i + r_j}{m n} + \frac{2}{n^2} \\ 0 &> \frac{2}{m^2}(1 - r_i + r_j) \\ r_i &> 1 + r_j \end{align}

This means that if the solution contains two values which differ from each other by more than one, it cannot be optimal (since moving the two values closer together will decrease the score). Therefore, in an optimal solution $r_i$ will take on at most two values, separated from each other by $1$. Let's call them $r$ and $r+1$. Calling the number of bins with $r$ results $x$, and the number of bins with $r+1$ results $x'$, we can write a system of equations:

$$n = x + x' \\ m = rx + (r+1)x'$$

We can solve for $x$ and $x'$ in terms of $r$:

$$x' = n - x \\ m = rx + (r+1)(n-x) \\ m = rx + rn - rx + n - x \\ m = (r+1)n - x \\ x = (r+1)n-m$$

Given that $0\leq x \leq n$:

$$0 \leq (r+1)n-m \leq n \\ 0 \leq (r+1) - \frac{m}{n} \leq 1 \\ \frac{m}{n} \leq r+1 \leq \frac{m}{n} + 1 \\ \frac{m}{n} - 1 \leq r \leq \frac{m}{n}$$

Since $r$ must be an integer, we have:

$$r = \left\lfloor \frac{m}{n} \right\rfloor$$

Substituting back in, we see that:

\begin{align} r + 1 &= \left\lfloor \frac{m}{n} \right\rfloor + 1 \\ x &= \left(\left\lfloor \frac{m}{n} \right\rfloor +1 \right)n - m \\ x' &= m - \left\lfloor \frac{m}{n} \right\rfloor n \end{align}

## 1.2 Score of an Optimal Algorithm

The score of the optimal algorithm described above gives us a way to compute the minimum possible score for a given $m$ and $n$:

$$\sum_{i=0}^{n-1}\left(\frac{r_i}{m} - \frac{1}{n}\right)^2 = x\left(\frac{r}{m}-\frac{1}{n}\right)^2+x'\left(\frac{r+1}{m}-\frac{1}{n}\right)^2 \\ = \left[\left(\left\lfloor \frac{m}{n} \right\rfloor +1 \right)n - m\right]\left(\frac{\lfloor m/n\rfloor}{m}-\frac{1}{n}\right)^2+\left[m - \left\lfloor \frac{m}{n} \right\rfloor n\right]\left(\frac{\lfloor m/n\rfloor + 1}{m}-\frac{1}{n}\right)^2$$

To simplify this expression, we can make use of the identity:

$$\left\lfloor \frac{m}{n} \right\rfloor = \frac{m}{n} - \frac{m\ \mathrm{mod}\ n}{n}$$

To prevent the equations from getting too long, I'll use $m' = m\ \mathrm{mod}\ n$:

$$\left[\left(\frac{m-m'}{n} +1 \right)n - m\right]\left(\frac{m-m'}{mn}-\frac{1}{n}\right)^2+\left[m - \frac{m-m'}{n} n\right]\left(\frac{m-m'+n}{mn}-\frac{1}{n}\right)^2 \\ = (m-m' + n - m)\left(\frac{m-m' - m}{mn}\right)^2+(m - m+m')\left(\frac{m-m'+n-m}{mn}\right)^2 \\ = \frac{(n-m')(-m')^2+(m')(n-m')^2}{(mn)^2} \\ = \frac{(n-m')(m')}{(mn)^2}(m' + n-m') \\ = \frac{1}{n}\left(\frac{m'}{m}\right)\left(\frac{n-m'}{m}\right)$$

Thus we can see that the score decreases as $m$ increases, and has local minima when $m'$ or $n-m'$ are close to zero (i.e. $m$ close to divisible by $n$). This agrees with our intuition.

## 1.3 Optimal Scores for Mapping a $k\mathsf{d6}$ to a $\mathsf{d100}$

Using the expression above, Here's a table of the best possible scores for each $k \le 10$:

 k       m  (m mod n)  score
---------------------------
0           1   1  0.990
1           6   6  0.157
2          36  36  0.0178
3         216  16  2.88e-4
4       1,296  96  2.29e-6
5       7,776  76  3.02e-7
6      46,656  56  1.13e-8
7     279,936  36  2.94e-10
8   1,679,616  16  4.76e-12
9  10,077,696  96  3.78e-14
10  60,466,176  76  4.99e-15


An unstated assumption was that the assignment of results to bins was the same on each roll. Some algorithms achieve a better average score by allowing the results of one roll to influence the next. However, the score of each individual roll is limited by the same maximum.

# 2 Optimal Expected Number of Rolls

An algorithm can have an expected number of rolls less than the maximum number of rolls, while maintaining the same score. In fact, an algorithm can have a finite expected number of rolls even with an infinite maximum number. This is possible when the algorithm allows "early termination."

An algorithm maps each input roll (previously "result") to a corresponding output (previously "bin"). If an algorithm maps all rolls beginning with a certain prefix sequence to the same output, once that prefix has been rolled we know the output will be the same regardless of the subsequent rolls and we can stop rolling.

Pay careful attention to the terminology in the following sections: a roll is the roll of a single die, and a sequence or input is a list of rolls input to an algorithm

## 2.1 Bounding the Expected Number of Rolls

In order to compute the minimum expected number of rolls, I make the assumption that each roll is made with the same type of die. That is, if the first roll is a $\mathsf{d6}$, all the subsequent rolls will also be $\mathsf{d6}$s. Essentially, instead of rolling a large number of different dice, we roll one die over and over. (Note this restriction means that we cannot analyze algorithms that use another source of randomness such as the orientation of the die.) Assume we are using a $\mathsf{d}b$.

The expected number of rolls is the sum, over all inputs, of the probability of each input times its length. If the length of sequence $i$ is $k_i$, then the expected number of rolls $E$ is:

$$E = \sum_i k_i b^{-k_i}$$

Consider replacing a roll $\{x_1, x_2, x_3, \ldots, x_k\}$ with $b$ rolls all mapping to the same output as the original roll:

$$\{x_1, x_2, x_3, \ldots, x_k, 0\} \\ \{x_1, x_2, x_3, \ldots, x_k, 1\} \\ \vdots \\ \{x_1, x_2, x_3, \ldots, x_k, b-1 \}$$

The algorithm is still valid, since all possible rolls are mapped to outputs, and the probability of each output is the same. The change in $E$ is:

$$b\left[(k+1)b^{-(k+1)}\right]- k b^{-k} \\ = (k+1) b^{-k} - k b^{-k} \\ = b^{-k}$$

Thus, splitting an input increases $E$. Conversely, merging the set of inputs with a given prefix will decrease $E$. Therefore, choosing how many inputs of each length to assign to a given output can be solved by a greedy algorithm.

Imagine that the output space of the algorithm is represented by an interval of length $1$, and that each output is a sub-interval of length $p_i$ (the probability of that output). Each input is an interval of length $b^{-k}$, and the problem is to cover each output interval with a number of input intervals, with no overlap. The greedy algorithm does so optimally by repeatedly inserting the largest input (smallest $k$) that fits in the remaining space in the output.

Example: find the optimal distribution of inputs for $b=6$, $k=4$, $n=100$. We have:

$$m = 1296 \\ \left\lfloor \frac{m}{n} \right\rfloor = 12 \\ m' = 96$$

Remember that $p_i=r_i/m$, and $r_i=\lfloor m/n \rfloor + 0\text~{or}~1$, so:

$$p = \frac{12}{1296}~\text{or}~\frac{13}{1296}$$

$6^{-1}=1/6$ and $6^{-2}=1/36$ are both too big, but $6^{-3}=1/216$ is small enough to fit in both $p_i$:

\begin{align} p &= 2\times 6^{-3} + \frac{0}{1296} \\ &~\text{or}~2\times 6^{-3} + \frac{1}{1296} \end{align}

Finally, we fill up the remainder with multiples of $6^{-4}$:

\begin{align} p &= 2\times 6^{-3} \\ &~\text{or}~2\times 6^{-3} + 1\times 6^{-4} \end{align}

We can see that this process is just the expression of $p$ as a decimal in base $b$! With this in mind, I'll skip an analysis of the minimum $E$ for optimally-scoring algorithms of finite $k$, and jump straight to algorithms where $k$ is infinite.

## 2.2 Optimal Algorithm with Exact Distribution

With an infinite maximum $k$, the value of $m$ is also infinite, and the score of the algorithm drops to zero. This means that we can achieve an exactly uniform output distribution. This allows us to forget about $m$, $m'$, $x$, and other values that complicated the analysis. $p=1/n$ for all the outputs. We can find the decimal expansion of $p$ by using long division to divide $n$ into $1$.

Example: $b=6$, $n=100=244_6$. The long division is done in base-6.

      .0020543...
__________
244 ) 1
.532
----
.024
.02152
------
.00204
.001504
-------
.000132
.0001220
--------
.0000100


The final row is a power of the base, signifying that the decimal expansion repeats. Note that if we round the expansion to four digits, we get the same result as in the example for $k=4$.

With the expansion in hand, we can write an expression for $E$:

$$E = n\left[\sum_k d_k \times k \times b^{-k} \right] + (e+ k_r)\times b^{-k_r} \\ E = 100\left[2\times 3\times 6^{-3} + 5\times 5\times 6^{-5} + 4\times 6\times 6^{-6} + 3\times 7\times 6^{-7} \right] + (E+5)\times 6^{-5} \\ E = 14738/4665 \approx 3.159\ldots$$

The factor of $n$ appears because there are $n$ identical outputs contributing to $E$. $d_k$ is the $k$-th digit in the base-$b$ expansion of $1/n$, and $k_r$ is the number of repeating digits.

I don't know of a way to simplify the formula for $E$, since the decimal expansion can vary wildly with $b$ and $n$. For example, although $1/100=0.00\overline{20543}_6$ is a fairly short expansion, changing $n$ by $1$ results in $1/101=0.\overline{0020455351}_6$.

## 2.3 A Implementation of an Optimal Algorithm

Here I will describe one class of optimal algorithm, based on the interpretation of the input as a base-$b$ decimal such that the $k$-th roll is the $k$-th digit after the decimal point. For example, the input:

$$\{0, 4, 2, 2, 3\}$$

(with $b=6$) is equivalent to the decimal:

$$.04223_6$$

Note that inputs are uniformly distributed over the interval $[0,1)$.

Unlike the previous section where we grouped the inputs together based on their output, here I'll group the inputs based on size. The total amount of the interval occupied by inputs of length $k$ is $n d_k b^{-k}$. Note that this quantity is equivalent to the amount that we subtracted from the remainder at step $k$ of the long division, for example:

      .0020543...
__________
244 ) 1
.532 <= 100 * 2 * 6^-3
----
.024
.02152 <= 100 * 5 * 6^-5
------
.00204
.001504 <= 100 * 4 * 6^-6
-------
.000132
.0001220 <= 100 * 3 * 6^-7
--------
.0000100


Thus, the remainder at each stage is simply the amount of the interval remaining after all the inputs of length $k$ or less have been removed. This leads us to the algorithm, which I'll demonstrate for $b=6$, $n=100$.

Setup: put the remainders from dividing $n$ into $1$ in base $b$ into a table, along with the number of new digits for each step.

             roll 3
.024     =>   24   <--+
roll 2   |
.00204   =>  204      |
roll 1   |
.000132  =>  132      |
roll 1   |
.0000100 =>  100      |
roll 1 --+


For every output you need, start at the top of the table. Alternate between two steps:

• Roll the number of dice listed, and append their digits to the current value (which starts at zero).
• If the current value is greater than the number on the current row, return the difference of the two $\mathrm{mod}\ n$; otherwise continue to the next row.
• If you reach the end of the table, go back to the beginning, skipping the first row. (Note that if the decimal expansion terminates, the last remainder will be $0$ and you will never reach the end of the table.)

An example:

• Start with a current value of $0$.
• The first row is roll 3, so roll $\mathsf{3d6}$ and append their digits: $$\{6, 1, 5\} \to 015_6$$
• The next row is 24. Since $15_6 < 24_6$, continue to the next row.
• The next row is roll 2, so roll $\mathsf{2d6}$: $$\{4, 6\} \to 1540_6$$
• The next row is 204. Since $1540_6 \geq 204_6$, return the difference between the two, $\text{mod}\ 100$: $$1540_6 - 204_6 = 1332_6 = 344 \to \boxed{44}$$

Side note: The probability that you have to repeat the table at least once is equal to the last remainder: $.00001_6=1/7776\approx 0.013\%$. Assume that the DM and your entire party of five (six people total) make one roll per minute, every minute, for the next 10 years. That's a total of around $3\cdot 10^{7}$ rolls. Therefore the number of times you'll loop through the table will be around $\log_{7776}3\cdot 10^{7} \approx 1.9$!

• Still have to read through thoroughly- but first I have to stop giggling. "A bit more detail" indeed :-) – BmyGuest Dec 14 '15 at 8:51
• @BmyGuest It was true when I started four hours ago. By the time I finished I thought it was too funny to change =) – 2012rcampion Dec 14 '15 at 8:59
• Thank god this took you four hours to write. Any shorter and I'd feel like a failure as a human being. – Todd Wilcox Dec 14 '15 at 18:32
• This "bit more detail" will soon become a publication on its own right... :) – vsz Dec 16 '15 at 5:43
• While there a plenty of good answers on this now - and many of them have one or the other point to them - I feel this is the most complete mathematical answer to the solution, albeit not the most practical one. However, the questions was stated as a mathematical puzzle, so this weights in for this answer. – BmyGuest Dec 16 '15 at 15:44

Get 10 different d6 dices and describe them on paper. Next to each description, associate a unique number from 0 to 9.

Put all those dices in an opaque bag (you should have one to transport that near-infinite number of dices).

1. Shuffle the bag. Pick one die blindly and retrieve its value on the paper you wrote. Multiply that value by 10.
2. Shuffle the bag. Pick one die blindly and retrieve its value on the paper you wrote.

The fairness is maximal. The number of rolls (hum) is constant: 2.

If you feel the courage, use not 10 but 100 dice to reduce the rolls to 1.

Don't want a bag? Just arrange the dice randomly behind your back and pick without peeking.

Don't want a sheet of paper and pen? Memorize the numbers associated.

• A very clever out-of-the box solution! Although it only works if the dice are distinguishable, in my experience people with lots of dice usually have more than one color, so this probably would work in the real world. – 2012rcampion Dec 14 '15 at 0:30
• While this is a clever working solution, it circumvents the question. It basically comes down to "throw away your dice, take 100 pieces of paper, write numbers on them, and draw one of those at random instead of doing anything dice related" – DrunkWolf Dec 14 '15 at 7:31
• I could add a step to roll the die drawn and simply discard the result, couldn't I? ;) – Olivier Grégoire Dec 14 '15 at 9:00
• No, this is clearly not a math answer: it's a pragmatic answer for game leaders. And since I totally understand BmyGuest's question, as well as the context it's in, I will absolutely not mind if I don't get the accepted answer. – Olivier Grégoire Dec 14 '15 at 9:41
• @MarcoBonelli Sure it is! Maybe I should sneak in a lateral thinking tag now :-) But overall, I 've got so many instructive answers that I m having a hard time deciding on an accept. Each of them is helpful for me. – BmyGuest Dec 14 '15 at 13:10

We roll 3 dice $(D1,D2,D3)$, which we seperate spatially or in some other way (we used to use 3 different colors). We reroll D1 and D2 if they land on 6, and we reroll D3 if we it lands on a 5 or a 6. We repeat these rerolls until we have 3 numbers, $D1 \& D2 <= 5$, and $D3 <= 4$.

We then form our dice result by taking $(D1-1)*20+(D2-1)*4+D3$. This gives uniform numbers ranging from 1 $(1,1,1)$ to 100 $(5,5,4)$

Seeing as we're not allowed to roll an infinite amount of dice, we can stop after an arbitrary large amount of rerolls, and if we get there simply set the value to 51 (or any other). Since this chance goes to 0 the distribution tends to uniform.

small edit: you can drastically reduce the amount of rerolls needed by using 4 dice, and setting the value of D3 and D4 equal to 1 if the roll is below 3, and equal to 2 if the roll is 4+ and using the formula $(D1-1)*20+(D2-1)*4+(D3-1)*2+D4$

• Good idea, but @Zandar was right in his comment above. The algorithm has to (guarantee) to work with a finite number of dice and/or rolls. So "reroll until value fits" is not an option. I'll clarify that in the question, maybe... – BmyGuest Dec 13 '15 at 20:52
• @BmyGuest Yes, but with a finite number of rolls, one can just give up after the quota is exceeded and pick an arbitrary outcome (say, 100). Since the chance of this goes to 0, the distribution tends to uniform. – xnor Dec 13 '15 at 22:07
• @BmyGuest was about to adres that but xnor answered it for me, after an arbitrary large amount of rerolls we simply pick 51 as the outcome. This way we are arbitrarily close to the required distribution – DrunkWolf Dec 13 '15 at 22:35

As @MikeEarnest says, unless you put an upper limit on the number of rolls, you can always do better with more rolls. Since $6^n$ is never divisible by $100$, you can never be completely fair. With more rolls you can always get the unfairness lower.

The fact that $6^4=1296$ is very close to a multiple of $100$ means you can get very close to fair with $4$ rolls. You must have a way to order the rolls, either by die color or by order of rolling one die. Subtract one from each roll and view it as a base $6$ number from $0000_6=0_{10}$ to $5555_6=1295_{10}$ Now assign $13$ of the rolls to each of $96$ results and $12$ of the rolls to the other $4$ An easy way to do that is to divide the result by $99.7$ and throw away the remainder. There are $4$ choices with probability $\frac {12}{1296}$ and $96$ choices with probability $\frac {13}{1296}$ for error about $2.286E-6$ More rolls will always do better.

• Which is why, really, the re-rolling methods make more sense even though they're excluded here. You could have a bit of unfairness with guaranteed four rolls, or you could have perfect fairness in expected 3.24 rolls by rolling 3 dice, reading them as a base-6 number, re-rolling on >=200, and otherwise dividing by 2 (rounded down) – hobbs Dec 14 '15 at 7:21
• @hobbs And even assuming a huge number of trials like 10^9, the maximum number of rolls you'd expect to need per trial is only something like 21. – 2012rcampion Dec 14 '15 at 9:09

With $n$ rolls, there are $6^n$ possible outcomes. If you use fewer rolls, pretend you made additional rolls you ignored. Any algorithm maps an outcome to one of 100 values. So, an optimal algorithm is to partition the outcomes into 100 sets of as equal size as possible, differing by at most 1.

There are many ways to instantiate this partition with an algorithm. One is to treat the sequence of rolls as a number of base 6, with digits 0 through 5, and take the result modulo 100.

## Method: Accumulation Register

Each player needs four distinguishable dice and a piece of paper for logging. Identify the dice as "A", "B", "C", and "D". The log is initialized to "0". Each time a new percentile is needed, roll the four dice. Add the value $216(A-1) + 36 (B-1) + 6 (C-1) + D - 1$ to the currently logged value and reduce modulo $100$. (The phrase "reduce module 100" is equivalent to "keep only the last two digits" if everyone is working in base 10.)

Assuming fair dice, the rolling uniformly generates a value in $[0,1295]$. In a particular roll, $96$ outputs can be generated $13$ ways and $4$ outputs can only be generated $12$ ways. The fitness function $\sum (p_i-0.01)^2$ is then $96 \left( \frac{13}{1296} - 0.01 \right)^2 + 4 \left(\frac{12}{1296} - 0.01 \right)^2 \approx 2.3 \times 10^{-6}$. However, this is only a short-term effect. Over the long run (many times 100/4 = 25 rolls), this effect is evenly distributed over all possible outcomes. I.e., the fitness function decreases to zero as the number of rolls increases.

Variants:

• Using this method with three dice gives an increment in [0,215] and a fitness of $16 \left( \frac{3}{216} - 0.01 \right)^2 + 84 \left(\frac{2}{216} - 0.01 \right)^2 \approx 2.9 \times 10^{-4}$. Again over the long run, this decreases to zero.
• Using this method with nine dice gives an increment in [0,10077695] and a one-roll fitness of $96 \left( \frac{100777}{10077696} - 0.01 \right)^2 + 4 \left(\frac{100776}{10077696} - 0.01 \right)^2 \approx 3.8 \times 10^{-14}$.
• For $n$ dice, the one-roll fitness is roughly $10^{-1.5 n}$ and decreases to zero as many rolls are accumulated.

Several other answers here use the $36(A-1)+6(B-1)+(C-1)$ method, but do not arrange for the under-represented values to be (eventually) evenly distributed over all of $[0,99]$.

• Neat! So basically you're trading independence of rolls for a fair distribution. With four dice it looks like there'd be a slight trend to get worse rolls, except if you make a really poor roll you have a better chance to make a better roll. – 2012rcampion Dec 14 '15 at 9:26

Two dice with fair distribution

Two dices are sufficent. Take the orientation of one dice additionally. One of the four sides points towards the player. An exactly angle of 45° is unlikely. You mentioned, you have pen&paper?

Toss the red dice on a checkered paper. Not as complicated as measuring exact angle of dice in relation to the other ice or paper. We don't want a solution with a single dice, do we? Not practicable to draw exact angles smaller than 10°.

Toss the red dice on a checkered paper. You can distinguish the nearly 45° orientation by this way.

The dice sides are numbered from highest to lowest side 1-4.

Example

• Red side shows a 2. 2nd highest number: 26-50
• Red shows a 4: Segment 41 - 45 (range +3*5)
• Blue shows a 3: 43 is the result

Algorithm (base 4, 5, 5)

1. Toss a red and a blue dice.
2. Reroll dice showing a 6.
3. Orientation of the red dice determines the quarter (1-25, ... 76 - 100). Quick to use!
4. red dice r gives the number in a penta system. 5 * (r-1)
5. blue dice just gives the smallest influence. This barely has to be used in a roleplaying session.

Improved Algorithm (base 5, 4, 5)

Less cheating can be done if base 5 is taken first. The top of the dice can be seen by everyone and should have largest influence. Both have no approximation errors and feature few rerolls. Removing the rerolls of a 6 is easy, but less gameification.

B.t.w. Zero dice is not even a puzzle. You have paper and mathematicans: Draw a circle of with 36° segments on the paper. Label the ten segments from 0x to 9x. Spin your pen in the center. A second spin determines the 1 to 10.

Algorithm without reroll (not elegant)

There are 11 (6+5) possiblities for at least one six. We have to generate more information withouth using information dependant on the "red front side". 64 combinations by the blue front side and the two sides facing the other dice for two six. For a single six the mapping can be done 5 by 16 with two sides.

Avoid rerolling if the mapping does not fit: For this purpose turn the blue dice clockwise. This suits best the design goal for a finits number of dice throws: 1.

• Nice idea of using the orientation in addition to side. – BmyGuest Dec 15 '15 at 7:04
• Your pen-spinning thing at the end doesn't involve literal dice, but it's not pure computation. I would argue that you're effectively rolling a d10 twice, so, in the spirit of the question, it should count as two dice rolls. – Blacklight Shining Dec 16 '15 at 9:26
• OP gives us pen&paper and even mathematicians to use in a voodoo ritual. Yeah, I agree upon the 2 dice metaphor in mathematical sense. Well spotted. – Stefan Bischof Dec 16 '15 at 9:39
• @BmyGuest stated "The "fairest" algorithm wins. Only if two algorithms are equally fair, the one with less dice rolls wins. This algorithm fullfills your wins conditions better. 2012rcampion's answer is extensive and has beautiful maths. He demonstrates using a score, how close to a fair algorithm he is. However this answer features fair distribution with one roll of two dice. – Stefan Bischof Jan 3 '16 at 14:08
• While I personally like and up voted your solution, I have disregarded it in the sense of the puzzle, as it utilizes 'meta' dice information - exactly as your zero-dice solution or drawing from a bag. There are plenty (clever) solutions this way, and I did not originally think of them.But: As I did not label the puzzle as 'lateral thinking' I felt that I should accept the 'best' answer solely based on the dice-numbers. – BmyGuest Jan 3 '16 at 14:19

For each digit you roll two 6d

1) If the first dice is 6, it gets re-rolled.

2) If the second dice is 1, 2 or 3, you take the value of the first dice. If it is 4, 5 or 6, you add 5 to the second dice. Obviously, "10" is converted to "0".

Pros:

• Exact distribution, each number from 0 to 99 has the same possibilities.

• Extensible to as many decimal places as you want.

• No need of complicated lookup tables or calculations to get evidence.

• Only 4 rolls for number.

Cons: it may need some reroll (1/6 by digit).

• Not bad, it looks like you average only 2.2 rolls per digit (4.4 rolls per d100). You can probably get around the problem of infinite rerolls not being allowed by just returning a fixed number after a certain number of rerolls. – 2012rcampion Dec 14 '15 at 9:32
• @2012rcampion <pedantic>In fact, as it is stated by the OP, I expect to get a stop of rerolls (i.e., any number other than six) in a finite number of attempts, by the law of the big numbers. The issue is that I cannot give a maximum bound for that finite number. I can even give an upper bound within a high degree of probability (f. e. saying that with 100 rererolls it will be enough with a 1 - 6^100 probability).</pedantic> I understand that it is not what the OP meant, though. :-P – SJuan76 Dec 14 '15 at 12:21

Take $n$ dice, and roll them one at a time. Let $a_0=0$, and let $a_k=a_{k-1}+100(r_k-1)/6^k$, where $r_k$ is the result of the $k$th roll. Then round $a_n$ down to an integer and use it as the result.

This essentially divides the range into $6^n$ pieces and reassembles them into as close to an even 100 pieces as possible, and can be made arbitrarily precise by using increasing numbers of dice. Still working on the exact error, but I think this may be optimal for any number of dice.

• I think the error is the same as for my answer: $(6^k-100\lfloor 6^k/100 \rfloor)(100 - (6^k-100\lfloor 6^k/100 \rfloor))/(100\cdot 6^{2k})$ – 2012rcampion Dec 14 '15 at 9:22

I actually don't know what you mean with the metric but it's fairly simple to do with just 3 rolls that might have to be repeated.

on 111 it is considered 1
on 112 it is considered 2
...
on 121 it is considered 7
...
on 211 it is considered 37
...
on 354 it is considered 100

For any value higher reroll the three dice.

Basically it's $(\texttt{first_digit} - 1)\times 36 + (\texttt{second_digit} - 1)\times 6 + \texttt{third_digit}$

• I was going to suggest this. If you're not particularly excited about the algorithm being efficient, then this will give you a uniform distribution much like using 2d10. – Fimpellizieri Dec 13 '15 at 19:45
• @DrunkWolf well it's slightly different but uses the same idea. I don't speak from experience, figured it out just like that – Ivo Beckers Dec 13 '15 at 19:49
• Convert results of 4-6 on the first die to 1-3, and you retain your uniform distribution and only have 2/27 chance of having to reroll. – frodoskywalker Dec 13 '15 at 20:13
• @frodoskywalker nice catch! – Ivo Beckers Dec 13 '15 at 20:23

### A possibility focused on a low (and finite) number of rolls and practicality

Roll 3 dice as 3 digits of a base-6 number. You get 216 different results (which I will just arbitrarily call result number 1-216). If the result is in the range 1-200 just take (mod 100). If you roll a number in 201-216 range you have one of 16 results, which you map to numbers 0-99 depending on how many rolls you already had this evening. (so the first player maps to 0-15, the second player to 16-31, next player 32-47,... wrapping around after 99)

If calculating the error for a single throw, it is quite high (2/216 vs 3/216) but spread over the whole evening or multiple game sessions the error evens out, as each possible outcome has the same probability.

### For practicality:

You can write a mapping table for the throws 1-200 and use a marker on a second table for 201-216 which you move up one space after each throw above 200) I would also spread out the results of the >200 rolls. So the first player maps 201-216 to ( 0, 6, ...., 84, 90 ) the next player to (1,7...,85,91) so for a roll-playing game where the result of a roll is usually used like You have to roll higher than 68 to pass the test no player gets a perceived unfair advantage.

While one can create a $n$-digit senary number by simply throwing $n$ dice, one can also create binary and ternary numbers by grouping numbers together. Now one can look for a number $x=2^a3^b$ that is close to a power of ten to minimize "ramainder" reults that have to be distributed over all numbers. This requires to find a minumum of $\mod(log_{10}(2^a3^b),1)$. For up to fifty dice for instance this is found for $a=1$, $b=35$. The maximum number will be $M=10^{17}+63090197999408$. The $10^{17}$ can be distributed evenly over 100 numbers, while the $63090197999408$ can not: 92 numbers will receive a number range of $L=630901979994$ while the remaining 8 will be chosen for a range of $H=630901979995$ numbers. This yields the following probabilies:

• the 92 numbers: $(10^{15}+L)/T=0.009999999999999998$
• the 8 numbers: $(10^{15}+H)/T=0.010000000000000009$

So the 8 "high probability" numbers will be chosen $1.11\cdot10^{-13}\%$ more likely than the "low probability ones", which hopefully is neglible over the course of your campaign.

A few other optiumum versions:

• up to 10 dice: $a=9$, $b=9$, (9D6)
• up to 30 dice: $a=21$, $b=14$, (14D6, 7D2)
• up to 100 dice: $a=18$, $b=62$, (18D6, 44D3)
• up to 500 dice: $a=228$, $b=290$, (228D6, 62D3)
• There are some cases where you get slightly better results by looking for values that are slightly less than a whole number. Try $a,b=17,27$ for 30 and 50 dice. – 2012rcampion Dec 14 '15 at 10:30

Roll 3 dice, a red one, blue one, and green one, label the values as $r$, $b$, and $g$. Calculate:

$$N = 36 (r-1) + 6 (b-1) + g = 36r + 6b + g - 42$$

If $N > 108$, then subtract 108. (Effectively, you have relabeled the 4,5,6 on the red die as 1,2,3).

From here, you have two options for how to handle $N>100$:

1) Subtract 100. This gives an $8\%$ chance of unfairly giving a low roll, but is otherwise perfectly fair. Always uses $3$ rolls, the absolute minimum for determining 100 distinct values. Plus, your players will love you (assuming low rolls are good) for all the extra critical successes they are getting.

2) Reroll the dice when $N > 100$. This gives a perfectly fair distribution, usually completes in $3$ rolls, and has expected number of rolls required of $3 \div 0.92 \approx 3.26$ rolls.

This strategy is also very simple.

# An optimal algorithm with an optimal termination speed that can be done by humans

First the algorithm:

rolled = 0
max = 1
while(we have another die){
rolled = 6*rolled + rand(6)
max = 6*max
if(rolled/100 != max/100){
return rolled%100
}
max = max%100
rolled = rolled%100
}
return rolled


Here are just the most important points for the optimality of this algorithm.
The full proof is left the reader.

## It is easy:

All numbers have at most 3 digits. All divisions are with 100.

## This algorithm returns each value with an optimally equal propability:

To understand that these algorithm works you have to realize the following 3 points:

• The propability that rolled has a specific value (between $0$ and $max$) is always $\frac{1}{max}$.
• Under the condition that rolled doesn't has the same digit in the hundreds position then $rolled\%100$ is equally distributed.
• If $rolled$ and $max$ have the same digit in the hundreds position then taking modulo $100$ will keep these statements true.

## There can't be a faster algorithm:

• After n rolls there are $6^n$ possible outcomes.
• In $6^n\%100$ of those cases no algorithm could have terminated.
• The value of max is always $6^n\%100$.
• For all values in $[0, max-1]$ there is exactly one series of die throws to reach that specific values.
• There are exactly $max$ cases where the algorithm didn't terminated yet.

I know there are already better ideas out there, but I immediately thought of this one when I saw the question:

We can use binary counting: an even number on a die is a 1 and an uneven number on a die is a 0. Roll 7 dice (or one die 7 times) (2^7 = 128) and note the resulting binary code on a piece of paper. We now have a uniformly distributed number in the [0-128] range. We can scale this number to be in the [0~100] range by using Floor((X/128)*100). The floor will affect the distribution (I'm not exactly sure how much). But we can get arbitrarily close to perfect by using more dice (for example with 2^10 we get a number in [0~1024] which we can scale down and floor with less bias.

• Why switch from a base 6 solution (3 dice) to a base 2 solution (7 dice)? Your floor error is actually higher (216/200 vs 128/100) – Kyle Hale Dec 14 '15 at 18:14

The most simple approach

A D6 has an equal distribution. Take away your cheating dice! Statistically perfect dice will do the job.

1. Take a D6 and reroll if it shows a six. Otherwise the D6 indicates one of the five parts.
2. The last 20: Make 5 Segments of 4 pieces. Reroll if you have a 6.
3. The last 4: Reroll if you have a 5 or 6.

Praxis: Three different colored D6. At two black out the number 6. At one black out numbers 5 and 6 to remember rerolling.

Example: The "big" D6 a 2. The The "last 20" shows a 3. The "last 4" shows a 3.

33 = 20 + 10 + 3 = 20 * (2-1) + 5 * (3-1) + 1 * 3

Done by using three D6. Now statistically correct thanks to @DrunkWolf. The system uses the basis 20, 5 and 1 as digits.

• There are no D20's avaiable, that would make the thing trivial, one could simply roll 2D20 and divide the result of each individual die by 2. (rounding as normal ofcourse), – DrunkWolf Dec 14 '15 at 14:32
• 4d6 does not make a d20.. for one you can't roll below 4. Even if you were to use 4(d6-1) you wouldn't get an equal distribution, – DrunkWolf Dec 14 '15 at 14:48
• @DrunkWolf Adressed your statistical concerns. – Stefan Bischof Dec 14 '15 at 15:24
• this makes it identical to the top answer atm – DrunkWolf Dec 14 '15 at 15:26

If you are also allowed a basic clock displaying the current time to the second, you only need one die.

1. Establish the starting time (Ts).
2. Roll one die (value r). Non-rollers observe and agree on the throw time (Tt) to the second.
3. t = Tt - Ts.
4. Final value = r * (t mod 17 + 1). Reroll if r = 6 and t mod 17 = 15 or 16

You can also modify for smaller values than 17 second cycles. For example, you can also add a modulo to the number of cycles, and a conditional modulo within that a la leap years. It's fairly trivial to create a probabilistic model that equally generates values 1-100.

Of course, most of your entropy comes from when the die is thrown, rather than the throw itself.

My solution needs you to throw 2 identifiable dice (or throw them in order) per digit.

I like it because it's easy to compute by a human mind and builds the number digit per digit, so you are not faced with high numbers or base-changing stuff nor tables.

One digit is done by:

• rolling first dic to get a number between 1 and 5. This is done by rerolling any 6 and keeping any other result. To address the issue of possible infinite rolling, you can put an arbitrary limit of reroll (for example 4 reroll), and decide that when reached, the result would be an arbitrary number between 1-5 (for example: 5). Keep this number in mind.

• by rolling the second die, you get to add 5 or keep the previous number on odd or respectively even numbers.

You have your digit. Repeat the process to get your 1-100 number.

This solution is arbitrarily close to a perfect uniform distribution depending on the number of re-roll you are allowing yourself.

A nice variation

If the dice are actually recognisable, shuffle them in a box, pick only one at random, it'll decide if the '+5' bonus to applies to your result. You only have to throw it to finish the process of building your digit

• Wait, how can you get both a "0" and a "10" for the first digit in this scenario? – Kyle Hale Dec 16 '15 at 21:49
• @Kyle : you can't, as on a normal d10. Why would I need one ? As you are emulating d10, you get same results 1-10 or 0-9 depending how you interpret the face "0". I'm not sure I have understood your question fully. – vaab Dec 17 '15 at 8:12
• I see, my issue was your method only works if you use the 0-9 model and then add 1 to get 1-100. It's clear how it works, but you can't "get" a 1-100 number directly from your model as the first digit could be 0-10. – Kyle Hale Dec 17 '15 at 17:57

Even though this is listed as a mathematical problem no fancy mathematical solution is required.

My solution is based on that of @SJuan76.

1. Put 5 dice in an opaque bag. Each die has its '6' side covered with a different sticker in the range 1 to 5.
2. Pull a die from the bag at random, roll it to generate the number from one to five.
3. Roll an unstickered die. If the result is even add 5 to the result of the stickered die.
4. You now have a number from 1 to 10 (or 0) for the first digit. Repeat steps 1 - 3 for the second digit.

Only 6 dice required, the five in the bag plus another one, and exactly four d6 rolls per d100 and no time-consuming lookup tables.

You can even not use the unstickered die if you roll a stickered die with an even numbered sticker. With 6 dice in each of two colours and two bags you could even roll all 4 dice together and sum the result quickly.

## A calculator-based procedure.

Initialise your calculator with a random decimal fraction, You could start with π/6, or you could roll a few d6 to generate the seed.

Each time you need a d100, throw d6 three times. Each time add the number to the number currently in the calculator unless you throw a six; then divide by six (even if you throw a six).

After three throws, multiply the number by 100. The integer portion is your resulting d100; you should subtract this ready for the next throw.

Although any given throw will be slightly biased (216 rolls distributed between 100 results), the bias depends on your saved random number, and will therefore be random in the long term.

A solution that allows the number to be directly read from the dice in most cases:

Roll 3 identifiable dice, d1, d2 and d3. This gives 216 possible outcomes, so 2.16 outcomes should lead to each possible value.

200 of those outcomes can be mapped directly to the required output. Rather than requiring players to do multiplications by 6 and multi-digit modular arithmetic, I instead propose a straightforward lookup table as follows:

Set N := d2. If d1 = 3 or d1 = 6, add 3 or 6 to the value of N as necessary to bring it within the range 7-9.

If d1 <= 3, our result is equal to N * 10 + d3 (i.e. the digits are concatenated, and in particular when d1 <= 2, the value is shown right there on the other 2 dice with no other transformations required at all)

If d1 >= 4 and d3 <= 4, our result is equal to N * 10 + d3 + 6 (i.e. add 6 to the value of d3, but otherwise treat the same as before.

If d1 >= 4 and d3 = 5, our result is equal to N.

Together, these relatively simple rules cover 198 possibilities (of 216) with no "maths" involved, leaving only the 18 cases where d1 >= 4 and d3 = 6, and we've not generated the number 10 at all...

If d1 = d3 = 6 and d2 >= 5, our result is equal to 10.

If we have a result we can stop here. However, only 200 possible rolls mapped to a number, and 16 possible rolls don't have a defined result yet.

Roll another die, d4. It is recommended that this is rolled onto grid paper (as in Stefan Bischof's answer), as the orientation may be important, but not necessarily as critical as in that case (it will act only as the "decider" between two adjacent numbers).

Calculate X = (d1-4) * 36 + (d2 - 1) * 6 + d4

This will give a value between 1 and 96. Add 1 to X for values from 25 to 48, 2 for values from 49 to 72 and 3 for values from 73 to 96. This converts it to a distribution containing all integers from 1 to 99 except for multiples of 25.

Now consider the orientation of d4. For each of the possible 6 values of d4, there must be a defined reference position (e.g. the lowest numbered side face pointing north, or directly towards a nominated wall or similar).

Considering the current value mod 25 (which can be any value from 1 to 24, but not zero). Multiply this by 14.4 degrees (exactly 1/25 of a turn). If the cube were rotated clockwise towards the reference position, will it reach the reference position in less than this angle of rotation? If so, add 1 to the value of X. (25 dice identical to d4, and rotated to exactly the relevant angles could be glued to the table or squared paper for reference).

Almost all the time, the answer will be clear - only two critical orientations exist - one where d4 is almost exactly at the reference position, and one where rotating it by the specified angle would put it almost exactly at the reference position.

In those ambiguous cases (and only in those ambiguous cases), roll d5, and add one only if the value of d5 is odd.

All possible values are then selected with precisely equal probability, and a procedure that requires rolling at most 5 dice.

For 92.6% of rolls, only 3 dice are necessary, and the value requires almost no calculation. For the remaining 7.4% of rolls, 4 dice are necessary, with a 5th held in reserve to be rolled as a tie-breaker between two adjacent scores if the angle of the 4th die is not sufficient to resolve it.

I am very weak in the syntax that is the programming language known as mathematics, so please take my answer with enough salt.
Additionally I may be way off in the value of what I'm presenting (specifically in my usage of any actual math related terms).

So here it is:

The following requires no re-rolls (therefore meeting the finite number of rolls), covers all numbers from 0-99 (or 1-100 depending on how you're game system treats double 0 on 2d10), and, as far as my intuitive statistical analysis goes, (which may not be that far) is a reasonably even probability distribution across all numbers.

Additionally both possible solutions would be relatively simple to use.

Possible Solution 1

1. Roll 20d6
3. Any roll greater than 100 remove the 100s place and let the remaining value stand.

(NOTE: If you desire to have 0, then let a value of 100 represent 0 instead of 100).

Justification:
1/6th = 16.666666666666666666666666666667 (or rounded 17) 17 dice with a maximum value of 102 roughly cover most of 0-100 in 17-102.
3 dice with a maximum possible role value of 18 will assist in filling in the lower numbers 3-18.
the remainder above 100 of the 17 dice fill in for 1 & 2, while 3-17 fill in the missing numbers 1-17.
(NOTE: In my mind the intentional overlap of values improves the evenness[?] of the probability distribution/fairness.)

Possible Solution 2
Better, probably (because it may be more practical, though I suspect the probability distribution is similar...?):

1. Roll 1d6
2. Let the following ranges be represented by the value rolled
1= range 1-17
2= 18-34
3= 35-51
4= 52-68
5= 69-85
6= 86-100 (actually 102)
3. roll 3d6 and add the result to the base of your range you rolled earlier.
4. If the result is a number above 100 remove the 100s place and let it stand as the remaining value (101=01,103=03).
5. 100 either represents itself or 0

Essentially same justification as previous...

Final Note: I believe this method could potentially work for any dice standing in for 2d10/percentile dice.