The need for truly random data is quite common, but as any engineer can tell you, true random data is hard to come by. Computers are incapable of generating truly random data. Although some systems do a pretty good job of it, e.g. by collecting entropy from chaotic processes like keyboard and mouse usage, disk access, error corrections, etc., even these methods often fall short of cryptographic randomness.
There is, however, one class of number generator that is rather easy to come by and is about as close to truly random as one can come without using quantum events like radioactive decay. That device is the humble die.
Dice have been used for thousands of years to provide entropy for games, and they can also be used to provide entropy for computational needs. One particular task I often have is to generate a PIN for Second Life scripts to be used for security. This PIN is in the space of all 32-bit integers, meaning it is in the domain ![[-2^{32} \cdots 2^{32}-1]](http://s.wordpress.com/latex.php?latex=%5B-2%5E%7B32%7D%20%5Ccdots%202%5E%7B32%7D-1%5D&bg=T&fg=000000&s=0 "[-2^{32} \cdots 2^{32}-1]")
The easiest way I have found to do this is using four eight-sided (octohedral) dice, commonly used for Dungeons & Dragons, in which they are referred to as “d8″. The d8 I have are, as are most, number from 1 to 8, so I just treat 8 as 0 and use the other digits as they are, meaning each d8 gives me one octal digit. Four of these then give me twelve bits, which is three nibbles, so if I roll these 4d8 three times, I’ll get 36 bits, giving me the 32 bits I need plus four extra, which I just cut off the end.
In order to guarantee good random rolls, I keep the dice in a clear plastic tub (previously used for almonds) and just give it a good shake, then hold it at an angle so the dice line up along one of the bottom edges, then read them off left-to-right. Here’s an example:
| Roll 1 | Roll 2 | Roll 3 | |||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 3 | 4 | 1 | 0 | 1 | 4 | 7 | 1 | 1 | 1 | 2 | ||||||||||||||||||||||||
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | E | 1 | 0 | 6 | 7 | 2 | 4 | A | |||||||||||||||||||||||||||
Note that the last four bits are discarded, meaning onle the two most significant bits of the second-to-last d8 only count, and the entire last bit doesn’t count. The output value, in this case 0x0E106724, represents a full 32 bits of random data. I also use this method to generate chat channels, which are typically kept negative to prevent client eavesdropping. In these cases, I just force the most significant bit to 1, since that will guarantee a negative number.
That’s all there is to it! I have also seen 16-sided dice, which would generate 4 bits of data, so you could just roll 8d16 (or 4d16 twice (or 2d16 four times (or 1d16 eight times))) to generate the 32-bit integer, but d16 are an awful lot harder to find than d8.
If you’re stuck with six-sided dice, you can get two bits out of them by assigning 6 to 00 and re-rolling on 4 or 5. This would require twice as many dice (or rolls) as using d8, and could also be done with d4 (where 4 would be 0 and all other values would be their normal values). This does not skew results as the chance of landing on each of the valid sides is equal (1/6). d6 would be less efficient than d4, though, since 1/3 of rolls would be invalid (4 or 5). The reason there’s no way to make use of 4 or 5 is it would introduce skew, e.g. using the values directly would mean 6 and 7 would never be possible, and trying to do something like use the 1/3 bit of entropy provided by the extra faces would be more work than it would be worth, and I’m not certain it’s probabalistically even either.
Stay tuned for more random crap!
(pun very much intended)
Let’s say you shake some d6-s in a clear rectangular box, let them slip in line into a corner and then read them in order.
A d6 can land in one of 24 configurations: which of the six faces is facing you, and which of this face’s four sides is facing down. So you can easily extract 3 bits from each dice. First make sure each face has a defined “up” direction; mark an arrow if it doesn’t. Then assign each direction (up, left, right, down) a number 1-4; if the face shows 1-3, use the direction’s number; if the face shows 4-6, add 4 to the direction’s number. There is still unused entropy, because you treat 1,2,3 (and 4,5,6) as the same result, but you can’t divide the number of configurations by 2 so using that extra entropy would force you to re-roll sometimes.
Another source of entropy is the order of the dice in the line, N! for N dice. With 4 dice of different colours you can again get 3 bits without re-rolls.
A roll of 4d6 gives you 24^4 * 4! total configurations. This is divisible by 2^15, so you can get 15 random bits without ever needing re-rolls (3 from each die, 3 from the line order). If you pick a method that allows re-rolls, you can get up to 22 bits.
Thanks for the insight, Uri! As I was working with d8, which don’t line up very well against the wall of the tub, the thought of using the rotation as data didn’t even occur to me!
The dice don’t even need to be marked or gaming-style digital rather than pipped; you can read which number is up and which one is forward. For instance, if the up-face is 1, then the forward-face will be one of 2, 3, 4, or 5 (since opposing faces must add to 7). A simple rule for getting 3 bits out of a d6 would be:
most-significant bit = 1 if up-face is odd, else 0
The other two bits are the index of the ordered set of possible side values, so if 1 comes up and 3 is forward, the bits are 101 because 1 is odd (1xx) and 3 is the second (x01) possibility of {2, 3, 4, 5} in order.
This may sound a bit convoluted, but it’s really quite simple. There are only three possible side-sets, {2 3 4 5} for {1 6}, {1 3 4 6} for {2 5}, and {1 2 5 6} for {3 4}, so it should be pretty quick to think, “Five is up, four is forward, and (7 – 5 = 2) two is skipped, so four is the third possibility, which is two (bin 10) since it’s zero-based” and thus arrive at the index.
Allowing for re-rolls, you could just assign {6 1 2 3} to {0 1 2 3}, skip {4 5}, and get four bits out of each die (2/3 of the time, when {6 1 2 3} comes up).
I should point out, however, that the method suggested for extracting data from the *order* of the dice, if mathematically sound, is still a bit impractical. It would put a significant amount of added difficulty on reading the results of a roll such that simply rolling again to generate more bits would be a lot more reasonable. Additionally, this method would require the usage of color-coded or otherwise-differentiated dice.
Katie, your method of reading the rotation is nicely thought out. But I disagree about reading the line order: it shouldn’t be difficult at all. The first 2 bits come for almost free: mark one of the four dice, and use its position (1-4) in the line for an immediate 2 bits.
For the full 3 bits you’ll need dice of four different colours. If you have identical dice, paint the corners with permanent markers. Now, say you have four colours: red, green, yellow, blue. Look at the line and ask:
1. Where is the red? (4 possible answers)
2. Is the yellow left of the blue? (yes or no)
And you have 3 bits. It might be easier than reading a die.
Since we’re rolling several dice at once, it’s better to replace “re-roll” with “no result”. Simple example: roll four dice, translate {6 1 2 3} to 2 bits and {4 5} to no bits, so you end up with 0-8 bits.
Let’s use that within the method that uses rotation. We still haven’t used the information of which pair was vertical: {1 6}, {2 5} or {3 4}. We can get another bit by assigning {1 6}=1 and {2 5}=0. On {3 4} we don’t add bits. This gives an average of of 4 * (2/3) = 8/3 bits, or 16/3 for two rolls. As we already have 30 “guaranteed” bits, that means most of the time we can get to 32 bits with only two rolls, making 2/3 the noise and thus improving our relationship with other people in the household.
An even better idea is to join the “vertical pair” results from two dice. Then we have 9 possible results, so we get 3 bits, 8 out of 9 times. Since we only need 2 more bits over 30, the chance of not getting 32 bits in two rolls this way is (1/9)^4. If this happens to you, you don’t need a random number generator; you need an exorcist.