Faster than rand()?

Question

I'm working on an algorithm which needs to generate millions of numbers as fast as possible. Actually 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 big range at all. (I only need integer numbers below 1000)

Do you know something I could use ?

Thanks !

Edit :

I use this numbers for shuffling groups of less than 1000 entities.

I found out more about the "fast rand". And there is SSE version version which 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/

Answer 1

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;
}

Answer 2

Mersenne Twister algorithm is a quite fast yet balanced pseudo-random number generator.

Here is a sample implementation : http://fmg-www.cs.ucla.edu/geoff/mtwist.html

Answer 3

If you are using Intel Ivy Bridge processor, you could very well offload random number generation to hardware using RDRAND instruction.

This stack overflow article talks about the throughput of RDRAND.

You could also identify if the processor supports RDRAND and use hardware offload or else fall back to software implementation.