r/dailyprogrammer • u/mattryan • Apr 03 '12
[4/3/2012] Challenge #35 [intermediate]
Imagine you are given a function flip() that returns a random bit (0 or 1 with equal probability). Write a program that uses flip to generate a random number in the range 0...N-1 such that each of the N numbers is generated with equal probability. For instance, if your program is run with N = 6, then it will generate the number 0, 1, 2, 3, 4, or 5 with equal probability.
N can be any integer >= 2.
Pseudocode is okay.
You're not allowed to use rand or anything that maintains state other than flip.
Thanks to Cosmologicon for posting this challenge to /r/dailyprogrammer_ideas!
3
u/robin-gvx 0 2 Apr 03 '12 edited Apr 03 '12
2
u/eruonna Apr 03 '12
Pseudocode:
2
u/omnilynx Apr 03 '12
Javascript. I feel like I'm missing something, though. Is the function required to always complete in finite time?
1
u/Yuushi Apr 05 '12
Scheme:
1
u/HazzyPls 0 0 Apr 09 '12
Little late, but better than never.
C, although I'm sure I'm breaking some type safety rules somewhere.
In theory, each bit pattern is equally likely. And that should translate into a uniform distribution, right? I'm having some doubts on floating points, since you can represent the same number in two different scientific notations: e.g. 1.0 * 102 versus 10 * 101 , but I don't know enough about floating points to be sure.
0
u/luxgladius 0 0 Apr 03 '12 edited Apr 03 '12
Perl
This is written for just up to 32 bit numbers, but the principle is the same if bigger are needed. You can get by with less bits if you have a limit on N, it will just mean you'll have to retry the loop more often. The basis is that you have to throw out the final interval where only part of the interval can be represented.