On Saturday 25 August 2007, suchismit mahapatra wrote: > hi folks, > just wanted to share something with you guys and get your views > on the problem at hand. > > even though this is not inherently a C or C++ language problem, > i am sure it will interest you ppl. > > what i have is a random5generator() which gives me values > 0,1,2,3 and 4 with equal probability. > > now the problem is to build a random7generator()(which would > give me 0,1,2,3,4,5 and 6 with equal probability) using the > random5generator() at hand. > > the easiest way to do it is of course using the > random5generator() function more than once and add the values and then use > the remainder or modulus function to get the values.
I'm not particularly great at this type of thing, but it seems that your approach is flawed. I'm hardly a mathematician, but some thoughts: It seems to me that you have 2 problems. 1) by just adding random numbers together you are introduce a bias towards numbers in the middle. (ie there are 5 different combinations for random[0] and random[1] that can add up to 4, but there is only 1 combination that will produce 0 or 8) 2) ideally the max number you produce has to be such that x % 8 = 7 or you introduce a bias towards smaller numbers. The easiest way to solve problem number 1 is to just use base 5 numbers. Then, if you generate 1 random number you get a range from 0-4 (in base 5), 2 random numbers gives you 0-44 (base 5, 24 in decimal), 3 gives you 0-444 (124 in decimal). That gives you an even and consistent distribution. No number is duplicated and there are no holes in the distribution. The second part of the puzzle is a little trickier. As far as I can tell, there is no base 5 number consisting of all 4s that will satisfy the x % 8 == 7 criteria. On the other hand, the more times run run random5() the less obvious the bias: Generating 1 random numbers: range: 0..4 (4) 0: 1 of 5 (20.00000%) 1: 1 of 5 (20.00000%) 2: 1 of 5 (20.00000%) 3: 1 of 5 (20.00000%) 4: 1 of 5 (20.00000%) 5: 0 of 5 (0.00000%) 6: 0 of 5 (0.00000%) 7: 0 of 5 (0.00000%) Generating 2 random numbers: range: 0..44 (24) 0: 4 of 25 (16.00000%) 1: 3 of 25 (12.00000%) 2: 3 of 25 (12.00000%) 3: 3 of 25 (12.00000%) 4: 3 of 25 (12.00000%) 5: 3 of 25 (12.00000%) 6: 3 of 25 (12.00000%) 7: 3 of 25 (12.00000%) Generating 3 random numbers: range: 0..444 (124) 0: 16 of 125 (12.80000%) 1: 16 of 125 (12.80000%) 2: 16 of 125 (12.80000%) 3: 16 of 125 (12.80000%) 4: 16 of 125 (12.80000%) 5: 15 of 125 (12.00000%) 6: 15 of 125 (12.00000%) 7: 15 of 125 (12.00000%) Generating 4 random numbers: range: 0..4444 (624) 0: 79 of 625 (12.64000%) 1: 78 of 625 (12.48000%) 2: 78 of 625 (12.48000%) 3: 78 of 625 (12.48000%) 4: 78 of 625 (12.48000%) 5: 78 of 625 (12.48000%) 6: 78 of 625 (12.48000%) 7: 78 of 625 (12.48000%) Generating 5 random numbers: range: 0..44444 (3124) 0: 391 of 3125 (12.51200%) 1: 391 of 3125 (12.51200%) 2: 391 of 3125 (12.51200%) 3: 391 of 3125 (12.51200%) 4: 391 of 3125 (12.51200%) 5: 390 of 3125 (12.48000%) 6: 390 of 3125 (12.48000%) 7: 390 of 3125 (12.48000%) Generating 6 random numbers: range: 0..444444 (15624) 0: 1954 of 15625 (12.50560%) 1: 1953 of 15625 (12.49920%) 2: 1953 of 15625 (12.49920%) 3: 1953 of 15625 (12.49920%) 4: 1953 of 15625 (12.49920%) 5: 1953 of 15625 (12.49920%) 6: 1953 of 15625 (12.49920%) 7: 1953 of 15625 (12.49920%) Generating 7 random numbers: range: 0..4444444 (78124) 0: 9766 of 78125 (12.50048%) 1: 9766 of 78125 (12.50048%) 2: 9766 of 78125 (12.50048%) 3: 9766 of 78125 (12.50048%) 4: 9766 of 78125 (12.50048%) 5: 9765 of 78125 (12.49920%) 6: 9765 of 78125 (12.49920%) 7: 9765 of 78125 (12.49920%) Generating 8 random numbers: range: 0..44444444 (390624) 0: 48829 of 390625 (12.50022%) 1: 48828 of 390625 (12.49997%) 2: 48828 of 390625 (12.49997%) 3: 48828 of 390625 (12.49997%) 4: 48828 of 390625 (12.49997%) 5: 48828 of 390625 (12.49997%) 6: 48828 of 390625 (12.49997%) 7: 48828 of 390625 (12.49997%) Generating 9 random numbers: range: 0..444444444 (1953124) 0: 244141 of 1953125 (12.50002%) 1: 244141 of 1953125 (12.50002%) 2: 244141 of 1953125 (12.50002%) 3: 244141 of 1953125 (12.50002%) 4: 244141 of 1953125 (12.50002%) 5: 244140 of 1953125 (12.49997%) 6: 244140 of 1953125 (12.49997%) 7: 244140 of 1953125 (12.49997%) Generating 10 random numbers: range: 0..4444444444 (9765624) 0: 1220704 of 9765625 (12.50001%) 1: 1220703 of 9765625 (12.50000%) 2: 1220703 of 9765625 (12.50000%) 3: 1220703 of 9765625 (12.50000%) 4: 1220703 of 9765625 (12.50000%) 5: 1220703 of 9765625 (12.50000%) 6: 1220703 of 9765625 (12.50000%) 7: 1220703 of 9765625 (12.50000%) Josh [Non-text portions of this message have been removed]
