# How to best obtain bit sequences from throwing normal dice?

Throwing normal dice, one can get sequences of digits in [0,5]. In practice, which is the best procedure to transform such sequences into a desired number of bit sequences?

• This previous question may be relevant. – Thomas Jan 30 '13 at 21:40
• Perhaps I should add that an example of a "practical" question would be: If a random number in [0, 2^1024-1] is required, how should one best go about to generate it as a bit sequence through throwing normal dice? – Mok-Kong Shen Jan 30 '13 at 22:07
• You could always discard die rolls corresponding to 4 and 5. Then each die roll produces two bits of entropy. – Stephen Touset Jan 30 '13 at 23:20
• How best to ? Slowly. – Cris Stringfellow Jan 31 '13 at 2:33

Thomas' first procedure produces 2 bits per roll with a probability of $\frac23$, i.e. it produces $\frac43 \doteq 1.333$ bits on the average. This can be improved as he describes, but it gets quite complicated soon.

Producing a single bit per roll by taking the result mod two leads to $1$ bit per roll, which is not much worse. Combining the two simple methods like

1 -> 00
2 -> 01
3 -> 10
4 -> 11
5 -> 0
6 -> 1


is quite simple and produces $1+\frac23 = \frac53 \doteq 1.667$ bits per roll. AFAIK, this is the maximum you can get without aggregating the rolls.

You can apply this idea to two rolls and obtain $5$ bits with probability of $\frac{32}{36}$ and $2$ bits otherwise thus getting

$$2 + (5-2) \cdot \frac{32}{36} = 2 + \frac{3 \cdot 8}9 = 2 + \frac83 = \frac{14}3 = 4\frac23$$

bits for two rolls, i.e., $2\frac13 \doteq 2.333$ bits per roll, which is quite close to the theoretical maximum of $\log_2 6 \doteq 2.585$.

For a simple "implementation without computer", note that you can extract 1 bit directly from each roll and need to process the "rest" only (e.g. you can get the bit via $n \bmod 2$ and the rest via $\lfloor \frac{n-1}3 \rfloor$). This makes even combining 3 or 4 rolls using a small table easy.

### The exact procedure for two rolls

For simplicity, let's assume, each roll produces a number $n_i$ from the set $\{0, 1, \ldots, 5\}$.

• Extract one bit from each roll as $n_i \bmod 2$.
• Compute $3 \cdot \lfloor \frac {n_1}2 \rfloor + \lfloor \frac {n_2}2 \rfloor$, which is number $x \in \{0, \ldots, 8\}$
• In case of $x = 8$, you're out of luck and get nothing but the two bits from the first step.
• Otherwise, use $x \in \{0, \ldots, 7\}$ as the next three bits.

So, most of the time you get five bits. On the average, you get

$$\frac19 \cdot 2 + \frac89 \cdot 5 = \frac{42}9 = 4\frac23$$

bits as stated above.

There are nearly 5.170 bits in two rolls, but you can't extract 5 bits from them on the average without further aggregation.

• This family of procedures is optimal on the criteria of requiring the least dice throws to generate a given number of bits in the worst case. – fgrieu Jan 31 '13 at 20:07
• The method you described for both single and two rolls are very fine for the practice, I believe. One just have to look up in a table to write down the bits. For three rolls, however, there is a drop in efficiency, if my computation is not in error. (For the method described by Thomas the efficiency of using 3 rolls is also less than that of using 2 rolls.) – Mok-Kong Shen Jan 31 '13 at 22:35
• I have computed the values of efficiencies for different number of rolls in increasing order (in parentheses is value of the method described by Thomas) up to 100 rolls: 1 1.66667 (1.33333), 2 2.33333 (2.22222), 4 2.38272, 7 2.53178 (2.40800), 12 2.57454 (2.54856), 24 2.57598, 36 2.57708, 48 2.57712, 53 2.58454 (2.57951) – Mok-Kong Shen Feb 1 '13 at 11:02
• @Mok-Kong Shen: Yes, there's an efficiency drop for 3 rolls. You figures seem to be right. – maaartinus Feb 14 '13 at 2:02
• Perhaps I'm missing something obvious, but how do you get 5 bits with 2 rolls when each roll can give you at most 2 bits? – banzaiman Oct 29 '17 at 17:13

The obvious approach is to consider the following bit extraction algorithm:

1. Roll the die, producing an integer $n$ uniform in $\mathbb{Z}_6$.

2. If $n < 4$, return $n$ as two bits. Otherwise, go to 1.

This will return two uniform bits. The algorithm will always terminate, since the probability of recursion is equal to $\frac{2}{6}$ which is subcritical. A proof of correctness can be found in Dennis' post on this question.

How many dice rolls will the algorithm require? At least one, and arbitrarily many, but on average:

$$1 + \frac{2}{6} + \left ( \frac{2}{6} \right )^2 + \cdots = \sum_{t = 0}^\infty \left ( \frac{2}{6} \right )^t = \frac{3}{2}$$

That is, on average, the algorithm will require one and a half dice rolls. This is, of course, in accordance with information theory, which states that the Shannon entropy of an unbiased dice roll is equal to:

$$\log_2{ \left ( 6 \right )} = \log_2{\left ( 4 \right )} + \log_2{ \left ( \frac{3}{2} \right )}$$

However, this is not optimal. A lot of effort is wasted into compressing this into two uniform bits. Can we do better? Yes. For instance, consider rolling two dice together, drawing a uniform $n$ out of $\mathbb{Z}_{36}$. Then we can apply the same algorithm, but returning five bits instead of four, since $32 < 36$. Similarly, the probability of recursion is also lower at $\frac{4}{36}$ which means we are wasting less time and entropy.

We could also roll three dice, drawing $n$ out of $\mathbb{Z}_{216}$, but this is not optimal, even though we can extract seven bits, the probability of recursion is $\frac{88}{216}$ which is much higher than with even just a single die.

So, clearly, the "trick" is to select an integral number of dice such that $6^k$ is very close to (but greater than) a power of two, to minimize the probability of recursion and maximize our use of entropy. A computer program could be written to find the optimal number of dice to roll according to some efficiency metric, depending on your application's needs (or perhaps a general one exists).

The "intuition" behind this is that you can't use arbitrary amounts of entropy, since the bit is the absolute smallest amount of information possible. Any non-integral amount of entropy remaining must be "left behind" (here we use a recursive procedure to eliminate it, but there are other alternatives*).

However, if you can combine multiple such non-integral amounts of entropy through a non-destructive process (here, throwing multiple dice at the same time) you will naturally get more integral amounts of entropy ($0.5 + 0.5 = 1$) which allows you to make better use, of what you would otherwise have had to throw away.

*The answers to this question also suggest recursion is not an optimal approach in terms of efficiency.

• A quick calculation on my computer shows that throwing the dice 53 times would be best (from 1 to 100 dice throws) ... ah, 12 throws is a bit more practical and quite good too :) – Maarten Bodewes Jan 31 '13 at 0:21
• 12 throws gives you 31 bits, nice for an positive signed integer, but 32 would have been more practical :( – Maarten Bodewes Jan 31 '13 at 0:27
• Obviously 359 throws give 1.001066 for 928 bits, unbeaten within 10K throws (unless my precision is off) but you would get a sore arm. – Maarten Bodewes Jan 31 '13 at 0:33
• @owlstead Feel free to edit my answer to insert your results in, they would be a useful and welcome addition :) – Thomas Jan 31 '13 at 0:45
• What does "subcritical probability" mean? Wouldn't every probability $< 1$ be good for the expected number of rolls to be finite? – Paŭlo Ebermann Feb 6 '13 at 20:55

1 way to get 3 bits of entropy from a single die roll is as follows :

1. Roll the fair die
2. For 2,3,4,5 yield two bits {01,10,11,00} and go to 4, for 1 or 6 yield {1,0}.
3. For the number on the die appearing right-way-up to the thrower (0-179 degrees) yield {0} for the number on the die appearing upside-down to the thrower (180-359 degrees) yield {1} and go to 5.
4. For the number on the die being oriented within the first quadrant yield {00} for the other quadrants proceeding clockwise yield {01,10,11}.
5. Go to 1.

So for example I throw the following sequence 2(12 degrees), 3(111 degrees), 6 (98 degrees)

 2 -> 01, 12 degrees -> 0 , so 2(12) -> 010
3 -> 10, 111 degrees -> 1, so 3(111) -> 101
6 -> 0, 98 degrees -> 01, so 6(98) -> 001


Giving 010101001 169 for 3 throws.

Since number and rotations should both be random variables, the distribution is uniform, unbiased and random. The good thing is rotational distinctions between upper lower half, and all four quadrants are almost as easy to distinguish with the naked eye as the numbers themselves. Though on the boundaries there will be some error and bias, introducing a small additional noise into the signal.

Effectively this procedure amounts to the following : roll the die measuring its number and quadrant of rotation, and discard 1 bit of the quadrant information for the numbers {2,3,4 and 5}.

• Read the statement carefully: the input of the desired algorithm is "digits in [0,5]". – fgrieu Jan 31 '13 at 19:51
• Good point. I didn't see that. – Cris Stringfellow Jan 31 '13 at 19:56
• @CrisStringfellow I think you mean for step 2: "For 2,3,4,5 yield two bits {01,10,11,00} and go to 3, for 1 or 6 yield {1,0} and go to 4. – Aaron Toponce Jun 25 '18 at 5:07

Here is a specialization of this answer that is efficient in term of average entropy loss, and easily implemented.

Let $n$ be the number of faces on the dice ($n=6$ for a common dice). Let $b$ be the minimum value on the dice ($b=1$ on a common dice). Let $m$ be some large integer with $m≥n^2$. No value used will exceed $m$.

1. Set $r←0$, $s←1$.
2. If $s$ is even then proceed to 8.
3. If $s>m/n$ then proceed to 7.
4. Throw dice, getting $x$
5. Set $r←(x-b)+(n⋅r)$ and $s←n⋅s$
6. Proceed to 2 (optionally: or directly to 8 for even $n$).
7. If $r=s-1$ then proceed to 1.
8. Output $r\bmod 2$
9. Set $r←⌊r/2⌋$ and $s←⌊s/2⌋$
10. Proceed to 2.

The algorithm maintains $r$ uniformly random with $0≤r<s$, and its correctness follows from that.

As $m$ grows, the average proportion of lost entropy vanishes. However, the algorithm will from time to time (including initially) experience a longer period where it accumulates entropy and temporarily outputs at a low rate (or not at all for several consecutive dice throws, for odd $n$).

I would point out three things relating to this question.

• Normal dice
• In practice
• This is a cryptography forum

The first two points mean that you might be using biased dice. Normal dice are non homogeneous, perhaps chipped and might even be missing some spots. So their rolls would favour one outcome over another in the long run. They go to great lengths with expensive casino dice to eliminate as much bias as possible. They can't entirely, and hence the dice have sharp edges for grabbing the soft cushioning /pins of the craps table. Chaos plays it's part here in further reducing bias. And since this is cryptography, bias isn't a good thing if you're going to roll dice to generate encryption keys.

So the obvious solution is a von Neumann extractor. Roll twice. If roll 1 > roll 2, you get a "1". If roll 2 > roll 1 you get a "0". If roll 1 = roll 2, then output nothing and roll again. It's inefficient as you generate less than 1 bit per 2 rolls (it would be exactly 1 bit /2 rolls but you'll need a re roll every 6th pair). I think that it's actually 0.429 bits /roll in the long run. Not too bad considering they will be independent and identically distributed, or IID in NIST parlance.

The basic von Neumann algorithm can be much improved (x2) by considering multi pass tuples and erasures, but that level of maths is beyond me.

So in summary, you can generate a 256 bit AES key with less than 600 dice rolls and no Uranium or dodgy Intel RDRAND. Perhaps there's another way though?