Generate a random number using coin flips while guarenteeing termination

Question

The usual method to generate a uniform random number 0..n using coin flips is to build a rng for the smallest power of two greater than n in the obvious way, then whenever this algorithm generates a number larger than n-1, throw that number away and try again.

Unfortunately this has worst case runtime of infinity.

Is there any way to solve this problem while guaranteeing termination?

Answer 1

Quote from this answer https://stackoverflow.com/a/137809/261217:

There is no (exactly correct) solution which will run in a constant amount of time, since 1/7 is an infinite decimal in base 5.

Now ask Adam Rosenfield why it is true :)