[ALGO] Random number generator, with equal probability

RANDOM(a.b) is a random number generator that generates integers between a and b (inclusive), all equally likely.

Assuming we have an implementation of RANDOM(0.1), how can we implement RANDOM(a.b) - i.e. given we have a function that returns 0 OR 1 both with a probability of 1/2, how can we implement a function that returns integers from a to b (b > a), all with a probability of 1/n, where n = (b-a+1)

Source : Cormen - Problem 5.1-2 (randomized algorithms)


Similar problem :
At a restaurant, how can Veronica choose one out of three desserts with equal probability with the help of a coin?

Its on Gurmeet's site here  http://gurmeetsingh.wordpress.com/2008/09/12/puzzle-tossing-with-one-third-probability/

[Probability] Divide 100 marbles into two piles

How would you divide 50 black and 50 white marbles into two piles so that the probability of picking a white marble as follows is maximized: we first pick one of the piles uniformly at random, then we pick a marble in that pile uniformly at random?

Source : http://gurmeetsingh.wordpress.com/puzzles/