Quote:
Originally Posted by candybar
Not exactly. 6 and 4 are not co-prime but you can't get rand(6) out of rand(4) without the unbounded edge case. I think the following works: to get rand(n) out of rand(m) with a finite time guarantee, the set of prime factors of n has to be a subset of the set of prime factors of m.
Edit: apparently my pony's slow and this has already been pointed out lol.
This seems right except the part about it already having been pointed out. Where was that? This is how I tried to explain it to myself.
Ok so we have rand(m) and we want to generate rand(n) using k or fewer calls to rand(m) for some finite k. k calls to rand(m) will produce a sequence of return values and there are m^k such sequences, each equally probable. To get rand(n) as a uniform distribution we must partition those sequences into n equal sized groups, so m^k must be evenly divisible by n. Which is true if and only if the set of prime factors of n is a subset of the set of prime factors of m (as you stated).
The "or fewer" in "k or fewer calls" doesn't really matter. If some subsequences return early, we can consider that as mapping all possible full sequences that started with the subsequence to whatever value is returned.