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/

+3


source to share


4 answers


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

      



+3


source


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

+4


source


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.

+2


source


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.

+2


source







All Articles