 |  |  |  |  |  |  |  |
Is there a Poisson RNG that is seed-less?
Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.
 |
Hi guys,
I've been going around the web (whatever that means) in search of a seed-less poisson RNG. It's because I'm going to generate poisson random deviates for parallel-programming and I need it to be seed-less to ensure concurrent execution.
Cheers
I've been going around the web (whatever that means) in search of a seed-less poisson RNG. It's because I'm going to generate poisson random deviates for parallel-programming and I need it to be seed-less to ensure concurrent execution.
Cheers
•
•
Join Date: May 2004
Posts: 80
Reputation: 
Solved Threads: 5
Junior Poster in Training
If "Poisson RNG" means "pseudorandom number generator that generates Poisson-distributed numbers," you can generate your own from a uniform distribution; there's no need to locate a special Poisson generator if you already have a uniform PRNG that meets your requirements.
It sounds the real issue, though, is finding a generator that you can synchronize across multiple parallel processes--requests from different processes will still consume the number stream from a single generator. Suggestions:
It sounds the real issue, though, is finding a generator that you can synchronize across multiple parallel processes--requests from different processes will still consume the number stream from a single generator. Suggestions:
- Use single instance of any PRNG you want, and write a wrapper for it that buffers generated numbers and tracks requests for numbers, delivering the same sequence in the same order to each parallel process.
- Use separate instances of the same seeded PRNG in each parallel process, but generate the seed globally so each process will generate the same numbers.
- If you have a seedless generator that you can duplicate or which provides access to its initial state, use copies of the same seedless PRNG in each parallel process.
--smg
>It's because I'm going to generate poisson random deviates for parallel-programming
>and I need it to be seed-less to ensure concurrent execution.
No, you just need the seeding mechanism to work properly for your concurrent processes. However, you didn't specify what "work properly" means for you. Do you want each process to have the same sequence or do you want all generated numbers to be distributed randomly across all processes? The answer to that question determines what you should be looking for.
If you want each process to have the same sequence, then you only have an issue with multi-threading where all threads share the same resources (which includes the global seed if you're using something like C++'s rand).
The first way to deal with creating the same sequence is to re-seed the generator for every thread (or every process) if the generator is thread-aware. If it isn't thread-aware, the easiest solution in my opinion is to write a good generator that has the seed passed in as part of the interface:
This avoids the global resource and you can manage a separate state from each individual process/thread.
If you want the numbers to be randomly distributed across all of the processes, then with threads and a generator that isn't thread-aware, you're solid as long as you avoid deadlocks on the global seed. With real processes or a non-thread-aware generator, you have more of an issue and at that point it becomes a question of how do you communicate the seed state to every instance of the generator.
>and I need it to be seed-less to ensure concurrent execution.
No, you just need the seeding mechanism to work properly for your concurrent processes. However, you didn't specify what "work properly" means for you. Do you want each process to have the same sequence or do you want all generated numbers to be distributed randomly across all processes? The answer to that question determines what you should be looking for.
If you want each process to have the same sequence, then you only have an issue with multi-threading where all threads share the same resources (which includes the global seed if you're using something like C++'s rand).
The first way to deal with creating the same sequence is to re-seed the generator for every thread (or every process) if the generator is thread-aware. If it isn't thread-aware, the easiest solution in my opinion is to write a good generator that has the seed passed in as part of the interface:
#define N 624
#define M 397
#define A 0x9908b0dfUL
#define U 0x80000000UL
#define L 0x7fffffffUL
struct twister_state {
unsigned long x[N];
int next;
};
twister_state twister_seed ( unsigned long s )
{
twister_state state;
state.x[0] = s & 0xffffffffUL;
for ( int i = 1; i < N; i++ ) {
state.x[i] = ( 1812433253UL
* ( state.x[i - 1] ^ ( state.x[i - 1] >> 30 ) ) + i );
state.x[i] &= 0xffffffffUL;
}
return state;
}
unsigned long twister_rand ( twister_state& state )
{
unsigned long y;
unsigned long a;
/* Refill x if exhausted */
if ( state.next == N ) {
state.next = 0;
for ( int i = 0; i < N - 1; i++ ) {
y = ( state.x[i] & U ) | state.x[i + 1] & L;
a = ( y & 0x1UL ) ? A : 0x0UL;
state.x[i] = state.x[( i + M ) % N] ^ ( y >> 1 ) ^ a;
}
y = ( state.x[N - 1] & U ) | state.x[0] & L;
a = ( y & 0x1UL ) ? A : 0x0UL;
state.x[N - 1] = state.x[M - 1] ^ ( y >> 1 ) ^ a;
}
y = state.x[state.next++];
/* Improve distribution */
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680UL;
y ^= (y << 15) & 0xefc60000UL;
y ^= (y >> 18);
return y;
}If you want the numbers to be randomly distributed across all of the processes, then with threads and a generator that isn't thread-aware, you're solid as long as you avoid deadlocks on the global seed. With real processes or a non-thread-aware generator, you have more of an issue and at that point it becomes a question of how do you communicate the seed state to every instance of the generator.
I'm here to prove you wrong.
|
Other Threads in the Computer Science Forum
- Previous Thread: speech recognition system
- Next Thread: calculate time complexity of the algorithm
| Thread Tools | Search this Thread |
You need to join our community in order to build your list of favorite forums. You can visit the forum index for a listing of all forums.
Related Forum Features
Latest Computer Science Posts
- Today's Posts
- Unanswered Threads
ai algorithm algorithms amazon assignment assignmenthelp assignments automata battery bigbrother binary bittorrent bizarre bletchleypark blogging bomb business cern codebreaker compiler computer computers computerscience computertrackingsoftware conversion csc data dataanalysis dataintepretation development dfa dissertation dissertations dissertationthesis dissertationtopic ebook employment energy floatingpoint foreclosuresoftware fuel gadgets geeks givemetehcodez government graphics hardware history homeowners homeworkassignment homeworkhelp humor ibm idea ideas internet iphone ipod itcontracts jobs kindle laser laws linkbait lsmeans mainframes marketing mining mobileapplication msaccess netbeans networking news os p2p piracy piratebay programming research sas science security sex simulation software spying sql study supercomputer supercomputing sweden technology textfield turing turingtest two'scompliment uk virus warehouse ww2
