2
$\begingroup$

2 hours ago I thought I had this figured out, but now I am doubting myself and want someone to validate my algorithm.

I want to take a stream of k trusted random bits and convert it to groups of 5 digits in a uniformly distributed range from 0-99999. To do this I take k and truncate to a multiple of 32, let's say the result now has n bits where n = k - k % (4*8). To create one group of 5 digits we load 32 bits into a variable we'll call var_i. The result will be stored in var_e. To get 5 digits from 0-99999 takes 17 bits, so we perform the loop:

    for (int i = 0; i < 17; i++)
      var_e += ((var_i >> i) % 2) << i

this way we preserve only the first 17 bits. Then we perform var_e = var_e % 100000 to truncate var_e to 5 digits. var_e is now one complete block of 5 digits.

An alternative algorithm could be to just take a 32 bit number var_e and perform var_i = var_e % 100000. This would take just the last 5 digits of the 32 bit number, which fall into the range 0-99999.

These algorithms both waste nearly 50% of the input data, but it would be fairly easy to change the first one to accept 17 bits of input.

$\endgroup$
21
  • $\begingroup$ @fgrieu That answer does look helpful, and I will read it but I would like to try and learn some more from your comments to this question. I just realized I left off what may have been a crucial piece of information, the input stream is trusted random. 1) Yes it should be uniformly distributed, why do the two algorithms fail this? 2). One output for every 32 bits. Each 32 bit block is not related to its neighbor in any way. 3) Assume now that neither computational or data efficiency are important. $\endgroup$ – chew socks Apr 15 '13 at 5:56
  • 1
    $\begingroup$ Why would var_i = var_e % 100000give an unbiased output? For example, 0 is reached when var_e is 0 or 100000, but 99999 is reached only when var_e is 99999. $\endgroup$ – fgrieu Apr 15 '13 at 5:59
  • $\begingroup$ @fgrieu I see what you are saying about the bias from mod now, I hadn't considered that case. Is there a way to eliminate the most significant digit without creating a bias? $\endgroup$ – chew socks Apr 15 '13 at 6:18
  • 1
    $\begingroup$ @chewsocks The mod operator is the problem. You are reducing 2^17 different values into disjoint equivalence classes of 100000 elements (namely 0 to 99999). Since 100000 does not divide 2^17, you have one equivalence class which is smaller than 100000, and therein lies the bias (in fact, one equivalence class will have only 31072 elements instead of 10000, those elements are twice as likely to occur as the others - hardly a uniform distribution). For 2^32 the bias is smaller, but still present. a mod m is unbiased iff m divides the range of a. $\endgroup$ – Thomas Apr 15 '13 at 6:56
  • 1
    $\begingroup$ Related to this newer question, with a simple and practical answer; and this one. $\endgroup$ – fgrieu Apr 15 '13 at 20:43

Browse other questions tagged or ask your own question.