Fastest way to generate random integer from fair dice rolls Given I have a fair $n \in \mathbb{N}$-sided dice, and I want to generate an integer in the range of $[0, r), r \in \mathbb{N}$ with the same probability. I may roll the dice any number of times and stop anytime after observing the results. What is the best way to do this so that I do the least amount of expected dice rolls?
Intuitively, we can do it greedily so that anytime the number of possible outcomes is more than $r$, we take those outcomes out and re-roll when the rejection happens. In code, those will be something like (in the code, the dice numbers are zero-indexed):
def dice_rand(r, n):
   cur_val = 0
   max_val = 1
   while True:
      cur_val = n * cur_val + roll_dice(n)
      max_val = n * max_val
      d = floor(max_val / r)
      if cur_val < d * r:
         return floor(cur_val / d)
      cur_val = cur_val - d * r
      max_val = max_val - d * r 

Now I have problem figuring out the expected  dice rolls number for above algorithm. Also how do I prove the above algorithm is the most efficient?
 A: Any algorithm to roll an $r$-sided die with an $n$-sided die will inevitably "waste" randomness (and run forever in the worst case) unless "every prime number dividing [$r$] also divides [$n$]", according to Lemma 3 in "Simulating a dice with a dice" by B. Kloeckner.  In general, the greedy strategy is the best that can be done; another practical strategy is to use rejection sampling to get arbitrarily close to no "waste" of randomness (such as by batching multiple rolls of the $n$-sided die until $n^m$ is "close enough" to a power of $r$).
Take the much more practical case that $n$ is a power of 2 (and any block of random bits is the same as rolling a die with a power of 2 number of faces) and $r$ is arbitrary. In this case, this "waste" and indefinite running time are inevitable unless $r$ is also a power of 2.
See also these questions on Stack Overflow:

*

*https://stackoverflow.com/questions/63596813/frugal-conversion-of-uniformly-distributed-random-numbers-from-one-range-to-anot

*https://stackoverflow.com/questions/137783/expand-a-random-range-from-1-5-to-1-7
