First, the punchline. There is a method to generate a sequence of pseudo-random numbers six times faster than the standard C rand(). (138 million random integers per second over 26 million on my machine.) Even better, this method only requires seven lines of code.
int lfsr() //linear feedback shift register
{
const int taps = 0×8000000C; //this is a magic number
static int rnd_num = 1;
if(0×80000000 & rnd_num)
rnd_num = (rnd_num << 1) ^ taps;
else
rnd_num = rnd_num << 1;
return rnd_num;
}
A Linear Feedback Shift Register is a method used by hardware engineers to generate pseudo random numbers at extremely high speed. As in 3Gbps speed. When implemented in hardware, an LFSR actually takes fewer transistors than a counter. I’m not going to go into the theory of operation. If you’d like to explore that, wikipedia has a pretty good article.
Feel free to cut and paste the above function into whatever project you are working on.
The only downside of an LFSR is that it is totally unsuited to cryptography. A maximal period LFSR (like the one I provided) will go through every possible 32 bit integer. This means if you know the taps and the last number, you know all future numbers that will be generated. The more common function used for rand()–the Mersenne Twister algorithm–has more “hidden state” and one has to observe hundreds of outputs before being able to make this prediction.
So, don’t use this method if your purpose is cryptography. However, if you are trying to do a Montecarlo simulation or generating random inputs for unit tests, a Linear Feedback Shift Register is superior to the default C rand().
Edit:
You should only do this substitution in C. If you are working in a higher level language, the language overhead will probably cost more than using the built-in call to the default C implementation.