[Math][Python] Mixed radix, role-playing dices and PRNG

I'm not into RPG. But I always wondered, how to get some big number by throwing all these dices? When you have a coin, and you want to get a 16-bit number (16 bits of entropy), just throw it 16 times. When you have a D4 or D8 dice it's also easy -- the first can generate 2 bits at each throw, the second -- 3 bits. Having a D10 is good for generating decimal numbers too. But what is with other dices?

Let's see, what we have on the picture above (faces, range, mathematical term):

4 - 1..4 https://en.wikipedia.org/wiki/Tetrahedron
6 - 1..6 https://en.wikipedia.org/wiki/Cube
8 - 1..8 https://en.wikipedia.org/wiki/Octahedron
10 - 0..9 https://en.wikipedia.org/wiki/Pentagonal_trapezohedron
12 - 1..12 https://en.wikipedia.org/wiki/Regular_dodecahedron
20 - 1..20 https://en.wikipedia.org/wiki/Regular_icosahedron

How big a number can be generated? This is easy problem from combinatorics:

>>> 4*6*8*10*12*20
460800

How many bits of entropy?

>>> import math
>>> x=4*6*8*10*12*20
>>> math.log(x,2)
18.81378119121704

Here mixed radix system comes into play. A popular explanation is hour-minute-second time. There are 3 digits (not numbers). First digit in range of 0..23, second and third in 0..59.

In our case, each dice is digit. And here is a program that converts a number in this system into a decimal number.

#!/usr/bin/env python3

from operator import mul
import functools

def product(x):
    return functools.reduce(mul, x, 1)

def calc_weights(x):
    for i in range(1, len(x)):
        yield (product(x[i:]))
    yield (1)

def decode(weights, x):
    assert len(weights)==len(x)
    # FIXME: an element from x[] must not exceed an element from weights[]
    return sum(map(lambda x: x[0]*x[1], zip(weights, x)))

# decimal
x=[10, 10, 10, 10, 10, 10]
print ("total", product(x))
print ("weights:", list(calc_weights(x)))
print (decode(list(calc_weights(x)), [1,2,3,4,5,6]))
print ("")

# binary
x=[2, 2, 2, 2, 2, 2]
print ("total", product(x))
print ("weights:", list(calc_weights(x)))
print (decode(list(calc_weights(x)), [1,0,0,1,1,1]))
print ("")

# hours, minutes, seconds
x=[24, 60, 60]
print ("total", product(x))
print ("weights:", list(calc_weights(x)))
print (decode(list(calc_weights(x)), [10, 39, 49]))
print ("")

# dices:
x=[4, 6, 8, 10, 12, 20]
print ("total", product(x))
print ("weights:", list(calc_weights(x)))
print (decode(list(calc_weights(x)), [3, 4, 7, 9, 10, 17]))
print ("")
total 1000000
weights: [100000, 10000, 1000, 100, 10, 1]
123456

total 64
weights: [32, 16, 8, 4, 2, 1]
39

total 86400
weights: [3600, 60, 1]
38389

total 460800
weights: [115200, 19200, 2400, 240, 20, 1]
441577

Getting 18 bits of entropy by one throw, ha? Not bad? Increase the number of bits by increasing the number of dices. See also.

The mixed radix system is also used in Lehmer code, as factorial number system.

(the post first published at 20220705.)


List of my other blog posts.

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.