Faster than rand ()?
I am working on an algorithm that should generate millions of numbers as quickly as possible. In fact, I found out that the rand () function of my algorithm takes 75% of the process time.
So, I'm looking for something faster. And I don't need a large range. (I only want integers below 1000)
Do you know something that I could use?
Thank!
Edit:
I am using these numbers to shuffle groups of less than 1000 objects.
I learned more about fast rand. And there is a version of SSE version that is even faster and generates 4 numbers at a time.
https://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/
static unsigned int g_seed;
// Used to seed the generator.
inline void fast_srand(int seed) {
g_seed = seed;
}
// Compute a pseudorandom integer.
// Output value in range [0, 32767]
inline int fast_rand(void) {
g_seed = (214013*g_seed+2531011);
return (g_seed>>16)&0x7FFF;
}
The Mersen Twister algorithm is a fairly fast but balanced pseudo-random number generator.
Here's an example implementation: http://fmg-www.cs.ucla.edu/geoff/mtwist.html
On most systems, rand () is a pseudo-random number generator. So the code needs to be just a few shift + bit-OR operations and is capable of producing millions of numbers per second on a regular PC. You don't say what you get, what your hardware is, or what C library you are using, so it’s hard to see why your implementation is "slow".
Perhaps you can try to reuse the bits: take the least significant ten bits (= 1024 values), modulo 1000, to get the number range you want. Then shift and when you're done with a bit, call rand()
again for more bits.
If you are using an Intel Ivy Bridge processor, you can offload the random number generation to the hardware very well using RDRAND .
This Stack Overflow article talks about RDRAND throughput.
You can also determine if the processor supports RDRAND and uses hardware offloading and also opt out of software implementation.