Given a number \$n ≥ 2\$, a blackbox function \$f\$ that takes no arguments and returns a random integer in the range 0...n-1 inclusive, and a number \$m ≥ n\$, your challenge is to generate a random integer in the range 0...m-1 inclusive. You may not use any nondeterministic builtins or behaviour, your only source of randomisation is \$f\$.
The number you produce must be uniformly random. \$m\$ is not limited to powers of \$n\$.
One way to do this could be to generate \$\operatorname{ceil}(\log_n(m))\$ random numbers, convert these from base \$n\$ to an integer, and reject-and-try-again if the result's greater than or equal to \$m\$. For example, the following JS could do this:
function generate(n,m,f){
let amountToGenerate = Math.ceil(Math.log(m)/Math.log(n)) // Calculating the amount of times we need to call f
let sumSoFar = 0;
for(let i = 0; i < amountToGenerate; i++){ // Repeat that many times...
sumSoFar *= n; // Multiply the cumulative sum by n
sumSoFar += f() // And add a random number
}
if(sumSoFar >= m){ // If it's too big, try again
return generate(n,m,f);
} else { // Else return the number regenerated
return sumSoFar
}
}
An invalid solution could look something like this:
function generate(n,m,f){
let sumSoFar = 0;
for(let i = 0; i < m/n; i++){ // m/n times...
sumSoFar += f() // add a random number to the cumulative sum
}
return sumSoFar
}
This is invalid because it takes the sum of \$\frac{m}{n}\$ calls of f, so the randomness is not uniform, as higher/lower numbers have a smaller chance of being returned.
\$f\$ is guranteed to produce uniformly random integers, and can be independently sampled as many times as you want.
Instead of taking \$f\$ as a function, you may also take it as a stream or iterator of values, or an arbitrarily long list of values. The ranges may be 1...n instead of 0...n-1.
Scoring
This is code-golf, shortest wins!
moutputs fromf, if it has a single 0 output its position, otherwise retry. \$\endgroup\$