The rejection technique may never halt...(with an infinitesimally small probability of course)...
In the case of Dave's algorithm: if the following random_1_to_5() keeps returning 5. U1 = random_1_to_5(); while( U1 == 5 ); In the case of Ankur's algorithm if rand_5() keeps returning 2 or Random_bit() keeps returning 1 I do not have any solutions or hints to go on...but it seems like a harder problem to find a solution with provably finite running time or prove that one such solution cannot exist. - Karthik --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---