The reason why finding a solution to this question is difficult is because
the combinations of rand5() function which we use ( eg. rand5() + rand5()%2
) leads to some numbers being generated more frequently than others. So the
problem would be solved if we could find a function which leads to each
output being generated an equal number of times ( once, or maybe more. )
5 * rand5() + rand5()
Looking at this function, it is easy to see that each value from 0 to 24
will be generated only once for every respective value that first and
second rand5() returns.
Suppose the first rand5() returns 0, then the second rand5() can return any
value from 0 - 4. Now see that no value from 0-4 could be generated by any
other combination. When the value returned by the second rand5() is 1,
corresponding to the value returned by second rand5(), we could get 5 - 9.
Now we have each number from 0-24 appearing once. But simply returning the
mod of this value with 7 wouldn't lead to equal probability distribution as
the values 0 - 3 would be returned more times than 4-6. So to fix this
inequality, we ignore when the value of the function is more than 20. Now
doing mod with 7 will result in every number 0 - 6 being returned with
equal probability.
We could even have ignored the values above 6, or the values above 13, the
only difference being that it would take more number of calls to return a
rand7() result.
This way is non-deterministic i.e. we cannot say how many times the
function will be called before we get the rand7() result, but we can be
sure that whenever the function returns a value, it would have been as
probable as any other value from 0 - 6. Taking the mod of the result of the
function, there would be 3 ways in which each digit 0 through 6 can be
generated.
Implementation:
int rand7 ( ) {
int num = 5 * rand5 ( ) + rand ( ) ;
if ( num > 20 )
return rand7 ( ) ;
else
retutrn num % 7 ;
}
On Thu, Jun 21, 2012 at 12:44 PM, Abhishek Sharma <abhi120...@gmail.com>wrote:
> @umer
> it's not random,but biased
>
>
> On Wed, Jun 20, 2012 at 11:16 AM, Umer Farooq <the.um...@gmail.com> wrote:
>
>> Hmmm, true. That's what I expected in this solution. Similarly, we can
>> get 3 by (3,3) (1,2)
>>
>> However, did you take a look at the other solution I proposed? I guess
>> that solves the problem to some extent.
>>
>>
>> On Tue, Jun 19, 2012 at 7:18 PM, Sourabh Singh
>> <singhsourab...@gmail.com>wrote:
>>
>>> @Umer and Navin :
>>> 1 is generated by (1,3) only.
>>> 2 is generated by (1,1) and (2,3).
>>>
>>> so given solution is wrong
>>>
>>>
>>> On Tue, Jun 19, 2012 at 5:17 AM, Sourabh Singh <singhsourab...@gmail.com
>>> > wrote:
>>>
>>>> @ *ALL*
>>>>
>>>> please. post along with your method .
>>>> proof than it make's equal distribution over the given range.
>>>>
>>>> On Tue, Jun 19, 2012 at 4:47 AM, Navin Kumar
>>>> <algorithm.i...@gmail.com>wrote:
>>>>
>>>>> @Umer:
>>>>>
>>>>> rand(5) + (rand(5)%2): => it will never give 6 because for rand(7)
>>>>> range will be 0-6.
>>>>> So better try this: rand(5) + (rand(5)%3).
>>>>>
>>>>>
>>>>> On Tue, Jun 19, 2012 at 2:45 PM, Umer Farooq <the.um...@gmail.com>wrote:
>>>>>
>>>>>> rand(5) + (rand(5)%2);
>>>>>>
>>>>>>
>>>>>> On Tue, Jun 19, 2012 at 12:30 PM, Sourabh Singh <
>>>>>> singhsourab...@gmail.com> wrote:
>>>>>>
>>>>>>> @ sry
>>>>>>> condition should be:
>>>>>>>
>>>>>>> if(20*prob <= 500/7) :-)
>>>>>>>
>>>>>>>
>>>>>>> On Tue, Jun 19, 2012 at 12:26 AM, Sourabh Singh <
>>>>>>> singhsourab...@gmail.com> wrote:
>>>>>>>
>>>>>>>> @ALL
>>>>>>>>
>>>>>>>> Given a random number generator say r(5) generates number between
>>>>>>>> 1-5 uniformly at random , use it to in r(7) which should generate a
>>>>>>>> random
>>>>>>>> number between 1-7 uniformly at random
>>>>>>>>
>>>>>>>> i have seen this on many site's but not a single correct solution.
>>>>>>>> all solution's posted got rejected by someone else.:
>>>>>>>> plz.. suggest some algo :
>>>>>>>>
>>>>>>>> my aprroach:
>>>>>>>>
>>>>>>>> let's assume a rectangle :
>>>>>>>>
>>>>>>>> 100 |___________________
>>>>>>>> |___________________|______
>>>>>>>> 500/7 | | |
>>>>>>>> | | |
>>>>>>>> |___________________|______|
>>>>>>>> 0 1 2 3 4 5 6 7
>>>>>>>> now :
>>>>>>>>
>>>>>>>> let : num = rand(5);
>>>>>>>> prob = rand(5);
>>>>>>>>
>>>>>>>> if(prob <= rand(5))
>>>>>>>> print num
>>>>>>>> else
>>>>>>>> print 5 + num*(2/5)
>>>>>>>>
>>>>>>>>
>>>>>>>> --
>>>>>>>> You received this message because you are subscribed to the Google
>>>>>>>> Groups "Algorithm Geeks" group.
>>>>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>>>>> To unsubscribe from this group, send email to
>>>>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>>>>> For more options, visit this group at
>>>>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> You received this message because you are subscribed to the Google
>>>>>>> Groups "Algorithm Geeks" group.
>>>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>>>> To unsubscribe from this group, send email to
>>>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>>>> For more options, visit this group at
>>>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> --
>>>>>> Umer
>>>>>>
>>>>>> --
>>>>>> You received this message because you are subscribed to the Google
>>>>>> Groups "Algorithm Geeks" group.
>>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>>> To unsubscribe from this group, send email to
>>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>>> For more options, visit this group at
>>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>>
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>
>>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Umer
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Abhishek Sharma
> Under-Graduate Student,
> PEC University of Technology
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Anant Sharma
IIIrd year
Computer Enginering
Delhi Technological University
(formerly DCE)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
