Re: [algogeeks] Random Number generation

[Saurabh Kumar]

Take a look at  Linear Congruential
Generator
algorithm
for generating pseudo random numbers.

On 25 October 2012 16:58, bharat b  wrote:

> I heard that LINUX uses our past time mouse movement and keys pressed at
> time and something else to generate a random number.
>
>
> On Thu, Oct 25, 2012 at 4:07 PM, Anuj Khandelwal <
> anuj.cool.khandel...@gmail.com> wrote:
>
>> hey all,
>> Any idea to generate random number without using rand() function call ?
>> Any algorithms for random number generation ?
>>
>> --
>> Anuj Khandelwal
>> Final Year Undergraduate Student
>> Department of Computer Engineering
>> Malaviya National Institute of Technology, Jaipur
>> India
>> +91-9784678325
>>
>>  --
>> 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.

Re: [algogeeks] Random Number generation

[bharat b]

I heard that LINUX uses our past time mouse movement and keys pressed at
time and something else to generate a random number.

On Thu, Oct 25, 2012 at 4:07 PM, Anuj Khandelwal <
anuj.cool.khandel...@gmail.com> wrote:

> hey all,
> Any idea to generate random number without using rand() function call ?
> Any algorithms for random number generation ?
>
> --
> Anuj Khandelwal
> Final Year Undergraduate Student
> Department of Computer Engineering
> Malaviya National Institute of Technology, Jaipur
> India
> +91-9784678325
>
>  --
> 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.

[algogeeks] Random Number generation

[Anuj Khandelwal]

hey all,
Any idea to generate random number without using rand() function call ?
Any algorithms for random number generation ?

-- 
Anuj Khandelwal
Final Year Undergraduate Student
Department of Computer Engineering
Malaviya National Institute of Technology, Jaipur
India
+91-9784678325

-- 
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.

Re: [algogeeks] Random number

[Nitin Nizhawan]

following solution should work but it uses an array so its ST is O(N)

#include 
#include 
#define MAX 500
/** copied from wikipedia
  *
  */
unsigned m_w = time(NULL);/* must not be zero */
unsigned m_z = 300;/* must not be zero */

unsigned long get_random()
{
m_z = 36969 * (m_z & 65535) + (m_z >> 16);
m_w = 18000 * (m_w & 65535) + (m_w >> 16);
return (m_z << 16) + m_w;  /* 32-bit result */
}

// CLRS
void randomize(int list[],int size){
  for(int i=0;iwrote:

> "The space complexity is O(1)"
>
> I know about hash-tables. Can you implement with O(1) space complexity?
>
> On Mon, Aug 8, 2011 at 10:56 AM, 석문기  wrote:
> > Box-muller method is the good solution without a lot of computation
> overhead
> >
> > 2011/8/8 Puneet Gautam 
> >>
> >> You may be right..we cant remove collisions in O(1) time...
> >>
> >> But hey, hash table is still an effective way..
> >>
> >>
> >> On 8/8/11, Puneet Gautam  wrote:
> >> > Hey avoiding collisions using hash table can be real easy :
> >> > eg:
> >> > if 192 is the no generated let it hash to say index 7 of hash
> >> > table...so when it is again generated, it hashes to the same 7th index
> >> > of hash table, but we have a non zero value already present at that
> >> > index , 192 so we can reject this generated no. and proceed to the
> >> > next one..
> >> >
> >> > Whereas in an array , avoiding collision is a really hectic way...u
> >> > need to scan all the previously generated no.s for duplicacy...well
> >> > that aint gonna run in O(1) time..
> >> >
> >> > So implementing hash table reduces that overhead and runs it in O(1)
> >> > time..(it just has to check one if condition)with a bigger
> >> > constant.
> >> >
> >> > And moreover, we may even dont want an ordered sequence...just put the
> >> > generated no.s in hash table as soon as they are generated...dats it..
> >> >
> >> > then afterwards display that hash table..
> >> >
> >> > Did u get me...?
> >> >
> >> >
> >> > On 8/7/11, Gaurav Menghani  wrote:
> >> >> We can have a sorted sequence and display them in random order, but
> >> >> that is the same problem. How do we display them in random order? We
> >> >> need to have a sequence of random indices, that is the same problem
> as
> >> >> having random numbers, isn't it.
> >> >>
> >> >> Moreover, I don't think collisions can be avoided in less than O(n).
> >> >> We can have an efficient hash-table, but I am not sure how it can be
> >> >> done in O(1) or better.
> >> >>
> >> >> On Sat, Aug 6, 2011 at 12:37 PM, Puneet Gautam
> >> >> 
> >> >> wrote:
> >> >>> I rhink to avoid collisions altogether we should generate an ordered
> >> >>> sequence , in a dec. or inc. order and
> >> >>> display them randomly, i mean:
> >> >>>
> >> >>> Let say a[10] contains all the random no.s , map all the 10 indexes
> to
> >> >>> a hash table and then display the arrays with the hashed index...
> >> >>>
> >> >>> I think it may work...
> >> >>>
> >> >>> what say..?
> >> >>>
> >> >>>
> >> >>> On 8/5/11, Gaurav Menghani  wrote:
> >>  1. Get a good seed.
> >>  2. Increase the degree of the polynomial.
> >> 
> >>  This is no fixed algorithm, if you find that more than T steps have
> >>  passed and a new number has not been generated, you can always
> change
> >>  the polynomial. And, please remember it is a 'pseudo-random number
> >>  generator'. You can read the theory about PRNGs and LFSRs, all of
> >>  them
> >>  repeat.
> >> 
> >>  On Fri, Aug 5, 2011 at 7:14 PM, payel roy 
> >>  wrote:
> >> > How do you guarantee termination of your algorithm if duplication
> >> > occurs
> >> > ??
> >> >
> >> > On 5 August 2011 18:25, Gaurav Menghani <
> gaurav.mengh...@gmail.com>
> >> > wrote:
> >> >>
> >> >> You might want to read the theory on Pseudo-Random Number
> >> >> Generators
> >> >> [0] and Linear Feedback Shift Register [1]
> >> >>
> >> >> The basic way of generating a random number is taking up a
> >> >> polynomial,
> >> >> f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) %
> N,
> >> >> where i is the ith random number you want, and seed can be
> anything
> >> >> random available, for example, you can find the current
> millisecond
> >> >> using time.h functions.
> >> >>
> >> >> A simple implementation, without the time thing is below:
> >> >>
> >> >> #include
> >> >> using namespace std;
> >> >>
> >> >> int poly[10],pn,N,M;
> >> >> int get(int seed)
> >> >> {
> >> >>int t=0;
> >> >>for(int i=0;i >> >>{
> >> >>int res=poly[i];
> >> >>for(int j=1;j<=(i+1);j++) { res = (res*seed);
> >> >> if(res>=N)
> >> >> res%=N; }
> >> >>t+=res;
> >> >>if(t>=N) t%=N;
> >> >>}
> >> >>t=(t+seed);
> >> >>t%=N;
> >> >>return t;
> >> >> }
> >> >>
>

Re: [algogeeks] Random number

[Gaurav Menghani]

"The space complexity is O(1)"

I know about hash-tables. Can you implement with O(1) space complexity?

On Mon, Aug 8, 2011 at 10:56 AM, 석문기  wrote:
> Box-muller method is the good solution without a lot of computation overhead
>
> 2011/8/8 Puneet Gautam 
>>
>> You may be right..we cant remove collisions in O(1) time...
>>
>> But hey, hash table is still an effective way..
>>
>>
>> On 8/8/11, Puneet Gautam  wrote:
>> > Hey avoiding collisions using hash table can be real easy :
>> > eg:
>> > if 192 is the no generated let it hash to say index 7 of hash
>> > table...so when it is again generated, it hashes to the same 7th index
>> > of hash table, but we have a non zero value already present at that
>> > index , 192 so we can reject this generated no. and proceed to the
>> > next one..
>> >
>> > Whereas in an array , avoiding collision is a really hectic way...u
>> > need to scan all the previously generated no.s for duplicacy...well
>> > that aint gonna run in O(1) time..
>> >
>> > So implementing hash table reduces that overhead and runs it in O(1)
>> > time..(it just has to check one if condition)with a bigger
>> > constant.
>> >
>> > And moreover, we may even dont want an ordered sequence...just put the
>> > generated no.s in hash table as soon as they are generated...dats it..
>> >
>> > then afterwards display that hash table..
>> >
>> > Did u get me...?
>> >
>> >
>> > On 8/7/11, Gaurav Menghani  wrote:
>> >> We can have a sorted sequence and display them in random order, but
>> >> that is the same problem. How do we display them in random order? We
>> >> need to have a sequence of random indices, that is the same problem as
>> >> having random numbers, isn't it.
>> >>
>> >> Moreover, I don't think collisions can be avoided in less than O(n).
>> >> We can have an efficient hash-table, but I am not sure how it can be
>> >> done in O(1) or better.
>> >>
>> >> On Sat, Aug 6, 2011 at 12:37 PM, Puneet Gautam
>> >> 
>> >> wrote:
>> >>> I rhink to avoid collisions altogether we should generate an ordered
>> >>> sequence , in a dec. or inc. order and
>> >>> display them randomly, i mean:
>> >>>
>> >>> Let say a[10] contains all the random no.s , map all the 10 indexes to
>> >>> a hash table and then display the arrays with the hashed index...
>> >>>
>> >>> I think it may work...
>> >>>
>> >>> what say..?
>> >>>
>> >>>
>> >>> On 8/5/11, Gaurav Menghani  wrote:
>>  1. Get a good seed.
>>  2. Increase the degree of the polynomial.
>> 
>>  This is no fixed algorithm, if you find that more than T steps have
>>  passed and a new number has not been generated, you can always change
>>  the polynomial. And, please remember it is a 'pseudo-random number
>>  generator'. You can read the theory about PRNGs and LFSRs, all of
>>  them
>>  repeat.
>> 
>>  On Fri, Aug 5, 2011 at 7:14 PM, payel roy 
>>  wrote:
>> > How do you guarantee termination of your algorithm if duplication
>> > occurs
>> > ??
>> >
>> > On 5 August 2011 18:25, Gaurav Menghani 
>> > wrote:
>> >>
>> >> You might want to read the theory on Pseudo-Random Number
>> >> Generators
>> >> [0] and Linear Feedback Shift Register [1]
>> >>
>> >> The basic way of generating a random number is taking up a
>> >> polynomial,
>> >> f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) % N,
>> >> where i is the ith random number you want, and seed can be anything
>> >> random available, for example, you can find the current millisecond
>> >> using time.h functions.
>> >>
>> >> A simple implementation, without the time thing is below:
>> >>
>> >> #include
>> >> using namespace std;
>> >>
>> >> int poly[10],pn,N,M;
>> >> int get(int seed)
>> >> {
>> >>        int t=0;
>> >>        for(int i=0;i> >>        {
>> >>                int res=poly[i];
>> >>                for(int j=1;j<=(i+1);j++) { res = (res*seed);
>> >> if(res>=N)
>> >> res%=N; }
>> >>                t+=res;
>> >>                if(t>=N) t%=N;
>> >>        }
>> >>        t=(t+seed);
>> >>        t%=N;
>> >>        return t;
>> >> }
>> >>
>> >> void setup_prng()
>> >> {
>> >>        pn=5;
>> >>        poly[0]=2; poly[1]=3; poly[2]=5; poly[3]=7; poly[4]=11;
>> >>        N=200; M=100;
>> >> }
>> >>
>> >> int main()
>> >> {
>> >>        setup_prng();
>> >>        for(int i=1;i<=M;i++)
>> >>                cout<> >>        return 0;
>> >> }
>> >>
>> >> Whenever there is a collision, you can increment the value passed
>> >> to
>> >> the random number generator and continue. However, I am not sure
>> >> how
>> >> to check for collisions in O(1) space.
>> >>
>> >> [0] http://en.wikipedia.org/wiki/Pseudorandom_number_generator
>> >> [1] http://en.wikipedia.org/wiki/Linear_feedback_shift_register
>> >>
>>

Re: [algogeeks] Random number

[석문기]

Box-muller method is the good solution without a lot of computation overhead

2011/8/8 Puneet Gautam 

> You may be right..we cant remove collisions in O(1) time...
>
> But hey, hash table is still an effective way..
>
>
> On 8/8/11, Puneet Gautam  wrote:
> > Hey avoiding collisions using hash table can be real easy :
> > eg:
> > if 192 is the no generated let it hash to say index 7 of hash
> > table...so when it is again generated, it hashes to the same 7th index
> > of hash table, but we have a non zero value already present at that
> > index , 192 so we can reject this generated no. and proceed to the
> > next one..
> >
> > Whereas in an array , avoiding collision is a really hectic way...u
> > need to scan all the previously generated no.s for duplicacy...well
> > that aint gonna run in O(1) time..
> >
> > So implementing hash table reduces that overhead and runs it in O(1)
> > time..(it just has to check one if condition)with a bigger
> > constant.
> >
> > And moreover, we may even dont want an ordered sequence...just put the
> > generated no.s in hash table as soon as they are generated...dats it..
> >
> > then afterwards display that hash table..
> >
> > Did u get me...?
> >
> >
> > On 8/7/11, Gaurav Menghani  wrote:
> >> We can have a sorted sequence and display them in random order, but
> >> that is the same problem. How do we display them in random order? We
> >> need to have a sequence of random indices, that is the same problem as
> >> having random numbers, isn't it.
> >>
> >> Moreover, I don't think collisions can be avoided in less than O(n).
> >> We can have an efficient hash-table, but I am not sure how it can be
> >> done in O(1) or better.
> >>
> >> On Sat, Aug 6, 2011 at 12:37 PM, Puneet Gautam  >
> >> wrote:
> >>> I rhink to avoid collisions altogether we should generate an ordered
> >>> sequence , in a dec. or inc. order and
> >>> display them randomly, i mean:
> >>>
> >>> Let say a[10] contains all the random no.s , map all the 10 indexes to
> >>> a hash table and then display the arrays with the hashed index...
> >>>
> >>> I think it may work...
> >>>
> >>> what say..?
> >>>
> >>>
> >>> On 8/5/11, Gaurav Menghani  wrote:
>  1. Get a good seed.
>  2. Increase the degree of the polynomial.
> 
>  This is no fixed algorithm, if you find that more than T steps have
>  passed and a new number has not been generated, you can always change
>  the polynomial. And, please remember it is a 'pseudo-random number
>  generator'. You can read the theory about PRNGs and LFSRs, all of them
>  repeat.
> 
>  On Fri, Aug 5, 2011 at 7:14 PM, payel roy 
> wrote:
> > How do you guarantee termination of your algorithm if duplication
> > occurs
> > ??
> >
> > On 5 August 2011 18:25, Gaurav Menghani 
> > wrote:
> >>
> >> You might want to read the theory on Pseudo-Random Number Generators
> >> [0] and Linear Feedback Shift Register [1]
> >>
> >> The basic way of generating a random number is taking up a
> >> polynomial,
> >> f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) % N,
> >> where i is the ith random number you want, and seed can be anything
> >> random available, for example, you can find the current millisecond
> >> using time.h functions.
> >>
> >> A simple implementation, without the time thing is below:
> >>
> >> #include
> >> using namespace std;
> >>
> >> int poly[10],pn,N,M;
> >> int get(int seed)
> >> {
> >>int t=0;
> >>for(int i=0;i >>{
> >>int res=poly[i];
> >>for(int j=1;j<=(i+1);j++) { res = (res*seed);
> >> if(res>=N)
> >> res%=N; }
> >>t+=res;
> >>if(t>=N) t%=N;
> >>}
> >>t=(t+seed);
> >>t%=N;
> >>return t;
> >> }
> >>
> >> void setup_prng()
> >> {
> >>pn=5;
> >>poly[0]=2; poly[1]=3; poly[2]=5; poly[3]=7; poly[4]=11;
> >>N=200; M=100;
> >> }
> >>
> >> int main()
> >> {
> >>setup_prng();
> >>for(int i=1;i<=M;i++)
> >>cout< >>return 0;
> >> }
> >>
> >> Whenever there is a collision, you can increment the value passed to
> >> the random number generator and continue. However, I am not sure how
> >> to check for collisions in O(1) space.
> >>
> >> [0] http://en.wikipedia.org/wiki/Pseudorandom_number_generator
> >> [1] http://en.wikipedia.org/wiki/Linear_feedback_shift_register
> >>
> >> On Fri, Aug 5, 2011 at 5:19 PM, payel roy 
> >> wrote:
> >> > Given a range 0-N, generate 'M' random numbers from the range
> >> > without
> >> > any
> >> > duplication. The space complexity is O(1).
> >> >
> >> > --
> >> > You received this message because you are subscribed to the Google
> 

Re: [algogeeks] Random number

[Puneet Gautam]

You may be right..we cant remove collisions in O(1) time...

But hey, hash table is still an effective way..


On 8/8/11, Puneet Gautam  wrote:
> Hey avoiding collisions using hash table can be real easy :
> eg:
> if 192 is the no generated let it hash to say index 7 of hash
> table...so when it is again generated, it hashes to the same 7th index
> of hash table, but we have a non zero value already present at that
> index , 192 so we can reject this generated no. and proceed to the
> next one..
>
> Whereas in an array , avoiding collision is a really hectic way...u
> need to scan all the previously generated no.s for duplicacy...well
> that aint gonna run in O(1) time..
>
> So implementing hash table reduces that overhead and runs it in O(1)
> time..(it just has to check one if condition)with a bigger
> constant.
>
> And moreover, we may even dont want an ordered sequence...just put the
> generated no.s in hash table as soon as they are generated...dats it..
>
> then afterwards display that hash table..
>
> Did u get me...?
>
>
> On 8/7/11, Gaurav Menghani  wrote:
>> We can have a sorted sequence and display them in random order, but
>> that is the same problem. How do we display them in random order? We
>> need to have a sequence of random indices, that is the same problem as
>> having random numbers, isn't it.
>>
>> Moreover, I don't think collisions can be avoided in less than O(n).
>> We can have an efficient hash-table, but I am not sure how it can be
>> done in O(1) or better.
>>
>> On Sat, Aug 6, 2011 at 12:37 PM, Puneet Gautam 
>> wrote:
>>> I rhink to avoid collisions altogether we should generate an ordered
>>> sequence , in a dec. or inc. order and
>>> display them randomly, i mean:
>>>
>>> Let say a[10] contains all the random no.s , map all the 10 indexes to
>>> a hash table and then display the arrays with the hashed index...
>>>
>>> I think it may work...
>>>
>>> what say..?
>>>
>>>
>>> On 8/5/11, Gaurav Menghani  wrote:
 1. Get a good seed.
 2. Increase the degree of the polynomial.

 This is no fixed algorithm, if you find that more than T steps have
 passed and a new number has not been generated, you can always change
 the polynomial. And, please remember it is a 'pseudo-random number
 generator'. You can read the theory about PRNGs and LFSRs, all of them
 repeat.

 On Fri, Aug 5, 2011 at 7:14 PM, payel roy  wrote:
> How do you guarantee termination of your algorithm if duplication
> occurs
> ??
>
> On 5 August 2011 18:25, Gaurav Menghani 
> wrote:
>>
>> You might want to read the theory on Pseudo-Random Number Generators
>> [0] and Linear Feedback Shift Register [1]
>>
>> The basic way of generating a random number is taking up a
>> polynomial,
>> f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) % N,
>> where i is the ith random number you want, and seed can be anything
>> random available, for example, you can find the current millisecond
>> using time.h functions.
>>
>> A simple implementation, without the time thing is below:
>>
>> #include
>> using namespace std;
>>
>> int poly[10],pn,N,M;
>> int get(int seed)
>> {
>>        int t=0;
>>        for(int i=0;i>        {
>>                int res=poly[i];
>>                for(int j=1;j<=(i+1);j++) { res = (res*seed);
>> if(res>=N)
>> res%=N; }
>>                t+=res;
>>                if(t>=N) t%=N;
>>        }
>>        t=(t+seed);
>>        t%=N;
>>        return t;
>> }
>>
>> void setup_prng()
>> {
>>        pn=5;
>>        poly[0]=2; poly[1]=3; poly[2]=5; poly[3]=7; poly[4]=11;
>>        N=200; M=100;
>> }
>>
>> int main()
>> {
>>        setup_prng();
>>        for(int i=1;i<=M;i++)
>>                cout<>        return 0;
>> }
>>
>> Whenever there is a collision, you can increment the value passed to
>> the random number generator and continue. However, I am not sure how
>> to check for collisions in O(1) space.
>>
>> [0] http://en.wikipedia.org/wiki/Pseudorandom_number_generator
>> [1] http://en.wikipedia.org/wiki/Linear_feedback_shift_register
>>
>> On Fri, Aug 5, 2011 at 5:19 PM, payel roy 
>> wrote:
>> > Given a range 0-N, generate 'M' random numbers from the range
>> > without
>> > any
>> > duplication. The space complexity is O(1).
>> >
>> > --
>> > 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.
>> >
>>
>>
>>
>> --
>>

Re: [algogeeks] Random number

[Puneet Gautam]

Hey avoiding collisions using hash table can be real easy :
eg:
if 192 is the no generated let it hash to say index 7 of hash
table...so when it is again generated, it hashes to the same 7th index
of hash table, but we have a non zero value already present at that
index , 192 so we can reject this generated no. and proceed to the
next one..

Whereas in an array , avoiding collision is a really hectic way...u
need to scan all the previously generated no.s for duplicacy...well
that aint gonna run in O(1) time..

So implementing hash table reduces that overhead and runs it in O(1)
time..(it just has to check one if condition)with a bigger
constant.

And moreover, we may even dont want an ordered sequence...just put the
generated no.s in hash table as soon as they are generated...dats it..

then afterwards display that hash table..

Did u get me...?


On 8/7/11, Gaurav Menghani  wrote:
> We can have a sorted sequence and display them in random order, but
> that is the same problem. How do we display them in random order? We
> need to have a sequence of random indices, that is the same problem as
> having random numbers, isn't it.
>
> Moreover, I don't think collisions can be avoided in less than O(n).
> We can have an efficient hash-table, but I am not sure how it can be
> done in O(1) or better.
>
> On Sat, Aug 6, 2011 at 12:37 PM, Puneet Gautam 
> wrote:
>> I rhink to avoid collisions altogether we should generate an ordered
>> sequence , in a dec. or inc. order and
>> display them randomly, i mean:
>>
>> Let say a[10] contains all the random no.s , map all the 10 indexes to
>> a hash table and then display the arrays with the hashed index...
>>
>> I think it may work...
>>
>> what say..?
>>
>>
>> On 8/5/11, Gaurav Menghani  wrote:
>>> 1. Get a good seed.
>>> 2. Increase the degree of the polynomial.
>>>
>>> This is no fixed algorithm, if you find that more than T steps have
>>> passed and a new number has not been generated, you can always change
>>> the polynomial. And, please remember it is a 'pseudo-random number
>>> generator'. You can read the theory about PRNGs and LFSRs, all of them
>>> repeat.
>>>
>>> On Fri, Aug 5, 2011 at 7:14 PM, payel roy  wrote:
 How do you guarantee termination of your algorithm if duplication occurs
 ??

 On 5 August 2011 18:25, Gaurav Menghani 
 wrote:
>
> You might want to read the theory on Pseudo-Random Number Generators
> [0] and Linear Feedback Shift Register [1]
>
> The basic way of generating a random number is taking up a polynomial,
> f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) % N,
> where i is the ith random number you want, and seed can be anything
> random available, for example, you can find the current millisecond
> using time.h functions.
>
> A simple implementation, without the time thing is below:
>
> #include
> using namespace std;
>
> int poly[10],pn,N,M;
> int get(int seed)
> {
>        int t=0;
>        for(int i=0;i        {
>                int res=poly[i];
>                for(int j=1;j<=(i+1);j++) { res = (res*seed); if(res>=N)
> res%=N; }
>                t+=res;
>                if(t>=N) t%=N;
>        }
>        t=(t+seed);
>        t%=N;
>        return t;
> }
>
> void setup_prng()
> {
>        pn=5;
>        poly[0]=2; poly[1]=3; poly[2]=5; poly[3]=7; poly[4]=11;
>        N=200; M=100;
> }
>
> int main()
> {
>        setup_prng();
>        for(int i=1;i<=M;i++)
>                cout<        return 0;
> }
>
> Whenever there is a collision, you can increment the value passed to
> the random number generator and continue. However, I am not sure how
> to check for collisions in O(1) space.
>
> [0] http://en.wikipedia.org/wiki/Pseudorandom_number_generator
> [1] http://en.wikipedia.org/wiki/Linear_feedback_shift_register
>
> On Fri, Aug 5, 2011 at 5:19 PM, payel roy  wrote:
> > Given a range 0-N, generate 'M' random numbers from the range without
> > any
> > duplication. The space complexity is O(1).
> >
> > --
> > 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.
> >
>
>
>
> --
> Gaurav Menghani
>
> --
> 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 opt

Re: [algogeeks] Random number

[Gaurav Menghani]

We can have a sorted sequence and display them in random order, but
that is the same problem. How do we display them in random order? We
need to have a sequence of random indices, that is the same problem as
having random numbers, isn't it.

Moreover, I don't think collisions can be avoided in less than O(n).
We can have an efficient hash-table, but I am not sure how it can be
done in O(1) or better.

On Sat, Aug 6, 2011 at 12:37 PM, Puneet Gautam  wrote:
> I rhink to avoid collisions altogether we should generate an ordered
> sequence , in a dec. or inc. order and
> display them randomly, i mean:
>
> Let say a[10] contains all the random no.s , map all the 10 indexes to
> a hash table and then display the arrays with the hashed index...
>
> I think it may work...
>
> what say..?
>
>
> On 8/5/11, Gaurav Menghani  wrote:
>> 1. Get a good seed.
>> 2. Increase the degree of the polynomial.
>>
>> This is no fixed algorithm, if you find that more than T steps have
>> passed and a new number has not been generated, you can always change
>> the polynomial. And, please remember it is a 'pseudo-random number
>> generator'. You can read the theory about PRNGs and LFSRs, all of them
>> repeat.
>>
>> On Fri, Aug 5, 2011 at 7:14 PM, payel roy  wrote:
>>> How do you guarantee termination of your algorithm if duplication occurs
>>> ??
>>>
>>> On 5 August 2011 18:25, Gaurav Menghani  wrote:

 You might want to read the theory on Pseudo-Random Number Generators
 [0] and Linear Feedback Shift Register [1]

 The basic way of generating a random number is taking up a polynomial,
 f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) % N,
 where i is the ith random number you want, and seed can be anything
 random available, for example, you can find the current millisecond
 using time.h functions.

 A simple implementation, without the time thing is below:

 #include
 using namespace std;

 int poly[10],pn,N,M;
 int get(int seed)
 {
        int t=0;
        for(int i=0;i>>>        {
                int res=poly[i];
                for(int j=1;j<=(i+1);j++) { res = (res*seed); if(res>=N)
 res%=N; }
                t+=res;
                if(t>=N) t%=N;
        }
        t=(t+seed);
        t%=N;
        return t;
 }

 void setup_prng()
 {
        pn=5;
        poly[0]=2; poly[1]=3; poly[2]=5; poly[3]=7; poly[4]=11;
        N=200; M=100;
 }

 int main()
 {
        setup_prng();
        for(int i=1;i<=M;i++)
                cout<>>>        return 0;
 }

 Whenever there is a collision, you can increment the value passed to
 the random number generator and continue. However, I am not sure how
 to check for collisions in O(1) space.

 [0] http://en.wikipedia.org/wiki/Pseudorandom_number_generator
 [1] http://en.wikipedia.org/wiki/Linear_feedback_shift_register

 On Fri, Aug 5, 2011 at 5:19 PM, payel roy  wrote:
 > Given a range 0-N, generate 'M' random numbers from the range without
 > any
 > duplication. The space complexity is O(1).
 >
 > --
 > 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.
 >



 --
 Gaurav Menghani

 --
 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.
>>>
>>
>>
>>
>> --
>> Gaurav Menghani
>>
>> --
>> 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@googlegrou

Re: [algogeeks] Random number

[Puneet Gautam]

I rhink to avoid collisions altogether we should generate an ordered
sequence , in a dec. or inc. order and
display them randomly, i mean:

Let say a[10] contains all the random no.s , map all the 10 indexes to
a hash table and then display the arrays with the hashed index...

I think it may work...

what say..?


On 8/5/11, Gaurav Menghani  wrote:
> 1. Get a good seed.
> 2. Increase the degree of the polynomial.
>
> This is no fixed algorithm, if you find that more than T steps have
> passed and a new number has not been generated, you can always change
> the polynomial. And, please remember it is a 'pseudo-random number
> generator'. You can read the theory about PRNGs and LFSRs, all of them
> repeat.
>
> On Fri, Aug 5, 2011 at 7:14 PM, payel roy  wrote:
>> How do you guarantee termination of your algorithm if duplication occurs
>> ??
>>
>> On 5 August 2011 18:25, Gaurav Menghani  wrote:
>>>
>>> You might want to read the theory on Pseudo-Random Number Generators
>>> [0] and Linear Feedback Shift Register [1]
>>>
>>> The basic way of generating a random number is taking up a polynomial,
>>> f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) % N,
>>> where i is the ith random number you want, and seed can be anything
>>> random available, for example, you can find the current millisecond
>>> using time.h functions.
>>>
>>> A simple implementation, without the time thing is below:
>>>
>>> #include
>>> using namespace std;
>>>
>>> int poly[10],pn,N,M;
>>> int get(int seed)
>>> {
>>>        int t=0;
>>>        for(int i=0;i>>        {
>>>                int res=poly[i];
>>>                for(int j=1;j<=(i+1);j++) { res = (res*seed); if(res>=N)
>>> res%=N; }
>>>                t+=res;
>>>                if(t>=N) t%=N;
>>>        }
>>>        t=(t+seed);
>>>        t%=N;
>>>        return t;
>>> }
>>>
>>> void setup_prng()
>>> {
>>>        pn=5;
>>>        poly[0]=2; poly[1]=3; poly[2]=5; poly[3]=7; poly[4]=11;
>>>        N=200; M=100;
>>> }
>>>
>>> int main()
>>> {
>>>        setup_prng();
>>>        for(int i=1;i<=M;i++)
>>>                cout<>>        return 0;
>>> }
>>>
>>> Whenever there is a collision, you can increment the value passed to
>>> the random number generator and continue. However, I am not sure how
>>> to check for collisions in O(1) space.
>>>
>>> [0] http://en.wikipedia.org/wiki/Pseudorandom_number_generator
>>> [1] http://en.wikipedia.org/wiki/Linear_feedback_shift_register
>>>
>>> On Fri, Aug 5, 2011 at 5:19 PM, payel roy  wrote:
>>> > Given a range 0-N, generate 'M' random numbers from the range without
>>> > any
>>> > duplication. The space complexity is O(1).
>>> >
>>> > --
>>> > 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.
>>> >
>>>
>>>
>>>
>>> --
>>> Gaurav Menghani
>>>
>>> --
>>> 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.
>>
>
>
>
> --
> Gaurav Menghani
>
> --
> 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.

Re: [algogeeks] Random number

[Gaurav Menghani]

1. Get a good seed.
2. Increase the degree of the polynomial.

This is no fixed algorithm, if you find that more than T steps have
passed and a new number has not been generated, you can always change
the polynomial. And, please remember it is a 'pseudo-random number
generator'. You can read the theory about PRNGs and LFSRs, all of them
repeat.

On Fri, Aug 5, 2011 at 7:14 PM, payel roy  wrote:
> How do you guarantee termination of your algorithm if duplication occurs ??
>
> On 5 August 2011 18:25, Gaurav Menghani  wrote:
>>
>> You might want to read the theory on Pseudo-Random Number Generators
>> [0] and Linear Feedback Shift Register [1]
>>
>> The basic way of generating a random number is taking up a polynomial,
>> f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) % N,
>> where i is the ith random number you want, and seed can be anything
>> random available, for example, you can find the current millisecond
>> using time.h functions.
>>
>> A simple implementation, without the time thing is below:
>>
>> #include
>> using namespace std;
>>
>> int poly[10],pn,N,M;
>> int get(int seed)
>> {
>>        int t=0;
>>        for(int i=0;i>        {
>>                int res=poly[i];
>>                for(int j=1;j<=(i+1);j++) { res = (res*seed); if(res>=N)
>> res%=N; }
>>                t+=res;
>>                if(t>=N) t%=N;
>>        }
>>        t=(t+seed);
>>        t%=N;
>>        return t;
>> }
>>
>> void setup_prng()
>> {
>>        pn=5;
>>        poly[0]=2; poly[1]=3; poly[2]=5; poly[3]=7; poly[4]=11;
>>        N=200; M=100;
>> }
>>
>> int main()
>> {
>>        setup_prng();
>>        for(int i=1;i<=M;i++)
>>                cout<>        return 0;
>> }
>>
>> Whenever there is a collision, you can increment the value passed to
>> the random number generator and continue. However, I am not sure how
>> to check for collisions in O(1) space.
>>
>> [0] http://en.wikipedia.org/wiki/Pseudorandom_number_generator
>> [1] http://en.wikipedia.org/wiki/Linear_feedback_shift_register
>>
>> On Fri, Aug 5, 2011 at 5:19 PM, payel roy  wrote:
>> > Given a range 0-N, generate 'M' random numbers from the range without
>> > any
>> > duplication. The space complexity is O(1).
>> >
>> > --
>> > 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.
>> >
>>
>>
>>
>> --
>> Gaurav Menghani
>>
>> --
>> 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.
>



-- 
Gaurav Menghani

-- 
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.

Re: [algogeeks] Random number

[payel roy]

How do you guarantee termination of your algorithm if duplication occurs ??

On 5 August 2011 18:25, Gaurav Menghani  wrote:

> You might want to read the theory on Pseudo-Random Number Generators
> [0] and Linear Feedback Shift Register [1]
>
> The basic way of generating a random number is taking up a polynomial,
> f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) % N,
> where i is the ith random number you want, and seed can be anything
> random available, for example, you can find the current millisecond
> using time.h functions.
>
> A simple implementation, without the time thing is below:
>
> #include
> using namespace std;
>
> int poly[10],pn,N,M;
> int get(int seed)
> {
>int t=0;
>for(int i=0;i{
>int res=poly[i];
>for(int j=1;j<=(i+1);j++) { res = (res*seed); if(res>=N)
> res%=N; }
>t+=res;
>if(t>=N) t%=N;
>}
>t=(t+seed);
>t%=N;
>return t;
> }
>
> void setup_prng()
> {
>pn=5;
>poly[0]=2; poly[1]=3; poly[2]=5; poly[3]=7; poly[4]=11;
>N=200; M=100;
> }
>
> int main()
> {
>setup_prng();
>for(int i=1;i<=M;i++)
>cout }
>
> Whenever there is a collision, you can increment the value passed to
> the random number generator and continue. However, I am not sure how
> to check for collisions in O(1) space.
>
> [0] http://en.wikipedia.org/wiki/Pseudorandom_number_generator
> [1] http://en.wikipedia.org/wiki/Linear_feedback_shift_register
>
> On Fri, Aug 5, 2011 at 5:19 PM, payel roy  wrote:
> > Given a range 0-N, generate 'M' random numbers from the range without any
> > duplication. The space complexity is O(1).
> >
> > --
> > 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.
> >
>
>
>
> --
> Gaurav Menghani
>
> --
> 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.

Re: [algogeeks] Random number

[Gaurav Menghani]

You might want to read the theory on Pseudo-Random Number Generators
[0] and Linear Feedback Shift Register [1]

The basic way of generating a random number is taking up a polynomial,
f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) % N,
where i is the ith random number you want, and seed can be anything
random available, for example, you can find the current millisecond
using time.h functions.

A simple implementation, without the time thing is below:

#include
using namespace std;

int poly[10],pn,N,M;
int get(int seed)
{
int t=0;
for(int i=0;i=N) 
res%=N; }
t+=res;
if(t>=N) t%=N;
}
t=(t+seed);
t%=N;
return t;
}

void setup_prng()
{
pn=5;
poly[0]=2; poly[1]=3; poly[2]=5; poly[3]=7; poly[4]=11;
N=200; M=100;
}

int main()
{
setup_prng();
for(int i=1;i<=M;i++)
cout Given a range 0-N, generate 'M' random numbers from the range without any
> duplication. The space complexity is O(1).
>
> --
> 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.
>



-- 
Gaurav Menghani

-- 
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.

[algogeeks] Random number

[payel roy]

Given a range 0-N, generate 'M' random numbers from the range without any
duplication. The space complexity is O(1).

-- 
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.

Re: [algogeeks] Random Number Generator

[surender sanke]

@nitish i think all above meant
3+rand(0,1)+rand(0,1)+rand(0,1)

surender

On Thu, Jul 7, 2011 at 12:36 AM, Nitish Garg wrote:

> If I understood you properly,
> Random(a,b)=(b-a)*Random(0,1)+**a
> ->Random(3, 6) = (3)*Random(0, 1) + 3
>= 3 + 3 = 6 or 0 + 3 = 3
> Just generates 3 and 6 with equal probability, what about 4 and 5?
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/I5enuEx37eQJ.
>
> 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.

Re: [algogeeks] Random Number Generator

[Nitish Garg]

If I understood you properly, 
Random(a,b)=(b-a)*Random(0,1)+a
->Random(3, 6) = (3)*Random(0, 1) + 3
   = 3 + 3 = 6 or 0 + 3 = 3
Just generates 3 and 6 with equal probability, what about 4 and 5?

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/I5enuEx37eQJ.
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.

Re: [algogeeks] Random Number Generator

[DeVaNsH gUpTa]

You can try
Random(a,b)=(b-a)*Random(0,1)+a









Thanks and Regards
DEVANSH GUPTA
MNNIT, ALLAHABAD

-- 
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.

Re: [algogeeks] Random Number Generator

[uttam tiwari]

i think a+rand(0,1)(b-a) will work

-- 
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.

Re: [algogeeks] Random Number Generator

[Nitish Garg]

Yes, I meant (a, mid) and (mid+1, b) only.
It now looks to me as the method I proposed will work well if the numbers in 
the range are a power of 2, in which case the division will be ideal.
Still looking a solution for any general range.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/s8InuwZYlOsJ.
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.

Re: [algogeeks] Random Number Generator

[sunny agrawal]

Oops ...
my method will also not work as probabilities will not be equal !!!

On Wed, Jul 6, 2011 at 11:29 PM, sunny agrawal wrote:

> For RNG in range [a,b] first thing is that all numbers should be generated
> with equal probability.
> in your case you are considering mid in both the ranges so you can modify
> it like [a,mid],[mid+1,b]
>
> still I think this will work fine as far as the ranges get divided
> equally..
>
> like consider the case
> [3,5] so division will be [3,4],[5] still probabilities will not be equal.
>
> so answer should be
> make b-a calls to rand(0,1) and return a+sum of return values of all the
> calls
>
> On Wed, Jul 6, 2011 at 11:20 PM, Nitish Garg wrote:
>
>> Describe an implementation of Random(a, b) that only make calls to
>> Random(0, 1)?
>> Well I am thinking this way:
>>
>>- Divide the range (a,b) in to 2 parts like (a, mid) and (mid, b)
>>where mid = (a+b)/2
>>- Select one of the range using a call to Random(0, 1).
>>- Then continue dividing the new range and selecting a new based on a
>>call to Random(0, 1) until we have two elements left.
>>- From the two elements one can easily be selected by a call to
>>Random(a, b).
>>
>> Is this approach correct? Or something else can be done?
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/kCRJ22w0_wMJ.
>> 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.
>>
>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
>


-- 
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee

-- 
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.

Re: [algogeeks] Random Number Generator

[sunny agrawal]

For RNG in range [a,b] first thing is that all numbers should be generated
with equal probability.
in your case you are considering mid in both the ranges so you can modify it
like [a,mid],[mid+1,b]

still I think this will work fine as far as the ranges get divided equally..

like consider the case
[3,5] so division will be [3,4],[5] still probabilities will not be equal.

so answer should be
make b-a calls to rand(0,1) and return a+sum of return values of all the
calls

On Wed, Jul 6, 2011 at 11:20 PM, Nitish Garg wrote:

> Describe an implementation of Random(a, b) that only make calls to
> Random(0, 1)?
> Well I am thinking this way:
>
>- Divide the range (a,b) in to 2 parts like (a, mid) and (mid, b) where
>mid = (a+b)/2
>- Select one of the range using a call to Random(0, 1).
>- Then continue dividing the new range and selecting a new based on a
>call to Random(0, 1) until we have two elements left.
>- From the two elements one can easily be selected by a call to
>Random(a, b).
>
> Is this approach correct? Or something else can be done?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/kCRJ22w0_wMJ.
> 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.
>



-- 
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee

-- 
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.

Re: [algogeeks] Random Number Generator

[Nitish Garg]

Don't think this will work.
Try rand(4, 7) : 4*rand(0,1) + 7 = 4*0 + 7 = 7 or 4*1 + 7 = 11(out of 
scope).

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/tJ40--FYSeoJ.
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.

Re: [algogeeks] Random Number Generator

[TIRU REDDY]

how about a*rand(0,1)+b?



On Wed, Jul 6, 2011 at 11:20 PM, Nitish Garg wrote:

> implementation of Random(a, b) that only make calls to Random(0, 1)

-- 
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.

[algogeeks] Random Number Generator

[Nitish Garg]

Describe an implementation of Random(a, b) that only make calls to Random(0, 
1)?
Well I am thinking this way:

   - Divide the range (a,b) in to 2 parts like (a, mid) and (mid, b) where 
   mid = (a+b)/2
   - Select one of the range using a call to Random(0, 1).
   - Then continue dividing the new range and selecting a new based on a 
   call to Random(0, 1) until we have two elements left.
   - From the two elements one can easily be selected by a call to Random(a, 
   b).

Is this approach correct? Or something else can be done?

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/kCRJ22w0_wMJ.
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.

Re: [algogeeks] random number generator

[Rahul Singal]

use the function which generate true 60% twice .

if first time its true and second time false then its true .(probability  .6
x .4 =.24 )
if first time its false and second time true then its false .(probability
.4 x .6 =.24 )
rest if it is both true or both false then call the procedure again
.(probability  .6 x .6 + .4x.4 =.52 )


Thanks
Rahul

-- 
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.

[algogeeks] random number generator

[saurabh agrawal]

Given a  function which returns true 60% time and false 40% time.

Using this function you have to write a function which returns true 50% of
the time.

-- 
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.

[algogeeks] random number [a....b]

[gold007]

how can we generate random values which lie in the range [a,b] or
wrire a function for the same

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] random number...

[ankur aggarwal]

  Given a random number generator that generates numbers in the range 1 to
5, how can u create a random number generator to generate numbers in the
range 1 to 7. (remember that the generated random numbers should follow a
uniform distribution in the corresponding range)

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] random number generator

[Monu Rathour]

i worked in *visual studio 8*,and there is a function  *rand()*  to generate
random numbers.
But now i have to work on *visual studio 6*, is there any such function?

--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---