Slice Algorithms for Counting in U-Dimensional Space

Abstract

This paper presents a computationally efficient algorithm for solving the following well-known die problem: Consider a “crazy die” to be a die with $n$ faces where each face has some “cost”. Costs need not be sequential. The problem is to determine the exact probability that the sum of costs from $U$ throws of this die is $\ge T$, $T\in \mathbb{R}$. Our approach uses “slice” volume computation in $U$-dimensional space. Detailed algorithms, complexity analysis, and comparison with traditional generating functions approach are presented.