Calculating odds of rolling a given total with a specified number of dice

[Dave Britten]

(06-16-2015 02:10 PM)Thomas Klemm Wrote:  Just tested it with HP-48GX.
You start with a 64-dimensional vector:

[0, 0, … , 0 , 0, 1, 1, 1, 1, 1, 1]

Run the discrete Fourier transform:

FFT

Transmogrify the result to a list of 64 complex numbers:

OBJ→
OBJ→
DROP
→LIST

{ (6,0) (5.5701807… }

Apply the 9th power (point-wise):

9 y^x

{ (10077696,0) (-8… }

Transmogrify back to a vector:

OBJ→
{ }
+
→ARRY

Compute the inverse Fourier transform:

IFFT

[ (.00000034,0) (.… ]

Drawback is that you have now an array of complex numbers that are nearly real.
Thus transmogrify back to a list and run:

ABS
0 RND

And finally you have the list of coefficients:

{ 0 0 0 0 0 0 0 0 0
0 1 9 45 165 495
1287 2994 6354
12465 22825 39303

Of course the list is a little longer than just that.

Cheers
Thomas

Very interesting stuff. I have to admit, I haven't done anything with FFTs before (though I have a general idea of what they're used for), so this is a bit out of my depth.

However, a simple C# version on my desktop gives results for 9 standard 6-sided (1-6) dice nearly instantaneously. The code is below; I've avoided heavily optimizing the array use to keep the indexing simple and make sure it's working correctly first, so there's a lot of zero padding for the lower powers of x. Note that results aren't necessarily symmetrical for for "unusual" die pools, so it can't just compute up to the halfway mark.

I should be able to do a C version for my 200LX, though the input parsing and mallocing will be a bit more labor-intensive. Everything else is just simple looping and arithmetic. I have a feeling trying to handle this with nested DOLISTs on a 48 would be fairly slow, but I might give it a shot.

Code:

    class Program {
        static void Main(string[] args) {
            List<int[]> dice = new List<int[]>(); //Input dice, transformed to polynomial coefficients (e.g. 1, 1, 1, 1, 1, 1)
            int[] d = null; //Single input die, for parsing
            int dq = 0; //Number of dice
            int[] result = null; //Accumulated result
            int[] lastresult = null; //Previous result, used in repeated multiplication
            int[] current = null; //Current die being multiplied with lastresult
            string line; //User input
            int q = 0; //Quantity (multiplicity) of input die
            List<int> inputs; //Parsed user input, with values of die faces (e.g. 1, 2, 3, 4, 5, 6)

            double p; //Total permutations

            //Input parsing loop
            while (true) {
                Console.Write("Die {0}? ", dq + 1);
                line = Console.ReadLine();
                if (String.IsNullOrWhiteSpace(line)) {
                    break;
                }
                Console.Write("Die {0} quantity? [1] ", dq + 1);
                if (!Int32.TryParse(Console.ReadLine(), out q)) {
                    q = 1;
                }
                inputs = line.Split(new char[]{' ', ',', ';'}, StringSplitOptions.RemoveEmptyEntries).Select(x => Int32.Parse(x.Trim())).ToList<int>();
                d = new int[inputs.Max() + 1]; //There's a zero element that remains 0, just to keep the indexing straight-forward. If I do a C version, it'll probably store the array length.
                for (int i = 0; i < inputs.Count; i++) {
                    d[inputs[i]]++;
                }
                for (int i = 0; i < q; i++) {
                    dq++;
                    dice.Add(d);
                }
            };

            //Calculation loop(s)
            lastresult = dice[0];
            p = (double)lastresult.Length - 1.0D; //Don't count the zero element.
            for (int i = 1; i < dq; i++) { //Loop through the dice.
                current = dice[i];
                p *= (double)current.Length - 1.0D; //Don't count the zero element.
                result = new int[lastresult.Length + current.Length - 1];
                for (int x = 0; x < lastresult.Length; x++) {
                    if (lastresult[x] == 0) {
                        continue;
                    }
                    for (int y = 0; y < current.Length; y++) {
                        result[x + y] += lastresult[x] * current[y];
                    }
                }
                lastresult = result;
            }

            //Result display loop
            bool skipzero = true;
            Console.WriteLine("Permutations: {0:n0}", p);
            Console.WriteLine("Total\tFreq\tProb");
            for (int i = 0; i < lastresult.Length; i++) {
                if (lastresult[i] == 0 && skipzero) {
                    continue;
                }
                skipzero = false;
                Console.WriteLine("{0}\t{1}\t{2:p4}", i, lastresult[i], (double)lastresult[i] / p);
            }
        }
    }

Usage:
Run the program, enter the values of the faces of each die, separated with spaces, commas, or semicolons. For example, "1 2 3 4 5 6", or "0 0 0 1 2 3". Enter the quantity after each given die, or press enter for the default of 1. When finished, enter a blank line when prompted for the next die faces.

Sample output:

Code:

Die 1? 0 0 0 1 2 3
Die 1 quantity? [1] 3
Die 4? 0 0 1 1 2 3
Die 4 quantity? [1] 2
Die 6? 0 0 1 2 3 4
Die 6 quantity? [1]
Die 7?
Permutations: 46,656
Total   Freq    Prob
0       216     0.4630 %
1       756     1.6204 %
2       1584    3.3951 %
3       2816    6.0357 %
4       4166    8.9292 %
5       5293    11.3447 %
6       6038    12.9415 %
7       6163    13.2094 %
8       5662    12.1356 %
9       4737    10.1530 %
10      3602    7.7203 %
11      2475    5.3048 %
12      1546    3.3136 %
13      871     1.8669 %
14      434     0.9302 %
15      193     0.4137 %
16      74      0.1586 %
17      23      0.0493 %
18      6       0.0129 %
19      1       0.0021 %