You are a programmer, you want to make a function rand(n) that takes an integer n>1 and returns a random integer in the range {1...n} with uniform probability.
At you disposal is a binary random number generator which generates 0's and 1's with equal probability (a fair coin) you can use it as many times as you want.
Can you do this and guarantee your program won't run forever?
You are a programmer, you want to make a function rand(n) that takes an integer n>1 and returns a random integer in the range {1...n} with uniform probability.
At you disposal is a binary random number generator which generates 0's and 1's with equal probability (a fair coin) you can use it as many times as you want.
Can you do this and guarantee your program won't run forever?
Share this post
Link to post
Share on other sites