Hi, I'm looking at this function from http://computer.howstuffworks.com/question697.htm
and wondering why we use the numbers, 1103515245, 12345? int rand()
{
random_seed = random_seed * 1103515245 +12345;
return (unsigned int)(random_seed / 65536) % 32768;
}
I know that the numbers generated are random between 0 and 32767, so 65536 is double that.
But why do we use 1103515245 (a prime?) and 12345 (not a prime?). Is it possible to use any big prime number + any random number or are they there for a specific reason?
thanks,
r_bewick
You can read about Linear congruential generators at Wikipedia. It has a decent explanation of what the numbers mean and what the typical requirements are for choosing them.
As the Wikipedia page says, you can get a much better PRNG by using an array as state, like the Mersenne twister does.
EDIT: Here's some code for you. I just wrote it and I haven't tested it much, but I have some experience writing PRNGs and I believe it should work well. // This code assumes 64-bit longs
class PRNG {
static unsigned long const state_size = 512;
unsigned long state[state_size];
unsigned long x;
int cursor;
public:
PRNG(unsigned long seed) : x(seed), cursor(0) {
// Use any simple method to generate the state from the seed
for (int i=0; i<state_size; ++i) {
x = x * 1103515245ul + 12345ul;
state = x;
}
}
unsigned long operator()() {
// Use a step of LCG
x = x * 0x7509A4D11AFB5161ul + 0xAAE6E3A00637DFA3ul;
// Mix higher and lower bits so lower bits are more random
x = (x << 32) | (x >> 32);
// Make use of the large state
x ^= state[cursor];
// Modify the state for later use
state[cursor] = x;
// Move down the array
cursor = (cursor + 1) % state_size;