@ Anant Sharma
Good one. it should work .
On Thu, Jun 21, 2012 at 9:43 PM, Anant Sharma <black.b...@gmail.com> wrote:
>
> 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.
--
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.
