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 <[email protected]> wrote: > How do you guarantee termination of your algorithm if duplication occurs ?? > > On 5 August 2011 18:25, Gaurav Menghani <[email protected]> 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 <[email protected]> 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 [email protected]. >> > To unsubscribe from this group, send email to >> > [email protected]. >> > 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
