Box-muller method is the good solution without a lot of computation overhead
2011/8/8 Puneet Gautam <puneet.nsi...@gmail.com>
> 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 <puneet.nsi...@gmail.com> 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 <gaurav.mengh...@gmail.com> 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 <puneet.nsi...@gmail.com
> >
> >> 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 <gaurav.mengh...@gmail.com> 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 <smithpa...@gmail.com>
> 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<iostream>
> >>>>>> using namespace std;
> >>>>>>
> >>>>>> int poly[10],pn,N,M;
> >>>>>> int get(int seed)
> >>>>>> {
> >>>>>> int t=0;
> >>>>>> for(int i=0;i<pn;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<<get(i)<<endl;
> >>>>>> 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 <smithpa...@gmail.com>
> >>>>>> 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.
> >>>
> >>>
> >>
> >>
> >>
> >> --
> >> 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.
>
>
--
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.
