its great to hear from you josh.
must say ur approach is interesting.
but the thing is even ur method doesnt give us the perfect random7generator.
talking abt my approach
will go through a few details here.
the thing u said the "middle" numbers being biased is correct.
but what we are considering here is just numbers from 0 to 6.
so when we encounter numbers which are greater than the above range, they
are made to fold to incorporate
them into the list. that is precisely why i took into account the remainder
operation.
when random5generator is called twice
we have possible values from 0 to 8. since we can accommodate
values from 0 to 6 only, so values 7 and
8 get included into the groups for 0 and 1.
these are the values we get
* * *cases for value 0* *cases for value 1* *cases for value 2* *cases
for value 3* *cases for value 4* *cases for value 5* *cases for value 6* * *
*rand5() twice* 3 3 3 4 5 4 3 * * *rand5()
thrice* 19 18 16 16 18 19 19 * * *rand5() four times* 91 93 91
88 87 87 88 * * *rand5() five times* 441 446 450 451 450 446
441 * * *rand5() six times* 2229 2224 2224 2229 2238 2243 2238
* * *rand5() seven times* 11177 11172 11158 11144 11144 11158
11172 * * *rand5() eight times* 55795 55823 55837 55823 55795
55776 55776 * * *rand5() nine times* 278965 278965 279007
279054 279073 279054 279007 * * *rand5() ten times* 1395153
1395064 1394998 1394998 1395064 1395153 1395195 * * *rand5()
eleven times* 6975563 6975629 6975563 6975408 6975277 6975277 6975408 * *
*rand5() twelve times* 34876933 34877154 34877440 34877571
34877440 34877154 34876933 * * *rand5() thirteen times*
174386031 174385614 174385614 174386031 174386538 174386759 174386538
-> min values -> max values
so u can see a patten here really.
without any ambiguity or bias towards any middle number to the extent that
boundary numbers 0 and 6 top the values list for certain number of
iterations.
this is definitely because of the use of modulus operator.
cheers
hulk
On 8/26/07, Josh Helmer <[EMAIL PROTECTED]> wrote:
>
> 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]
>
>
>
[Non-text portions of this message have been removed]
