Fast, fast random number generator
There are several algorithms, such as XorShift, that are really fast at generating random numbers that suit general use. Unfortunately I need to generate a random integer from [0 to 10] and using the function rand()
in my code results in a ~ 23% slowdown.
Question: What is the fastest way to generate an integer from [0 to 10]?
Edit: Information based on Brandon's comment:
The ~ 23% slowdown suggests that you are comparing it to something. What have you compared it to?
> I am doing rand ()% 10> 5.
also:
-
Using it
srand(time(0));
outside of the loop does nothing. -
rand() % 10
isolated ~ 19%, so comparison doesn't have a big impact on performance.
source to share
Xorshift is a great algorithm. Use it to create a buffer filled with random bits. Just because it fills the buffer 32 bits at a time, there is no reason why you should read them from the buffer 32 bits at a time. And since you want speed, you want to avoid separation (and mod). The only way to do this is to sample the rejection (also the only way to get completely unbiased numbers).
Since you only need 11 values (0 to 10), you only need 4 bits per sample. You reject 5 out of every 16, but since you will have 8 samples per 32 bits, this leaves you with an average of 5.5 outputs for each Xorshift iteration.
So, fill a large buffer from Xorshift, then convert that buffer to values (0 to 10) with the following:
for (int b = 0; b < sizeof inbuf; b += 1) {
uint8_t v = ((uint8_t *)inbuf)[b];
if ((v & 0x0F) < 10) { *outbuf++ = v & 0x0F; }
if (((v >> 4) & 0x0F) < 10) { *outbuf++ = ((v >> 4) & 0x0F; }
}
Make the outbuf
byte array twice as large inbuf
and it will be approximately 11/16 full. Fill both buffers as needed.
source to share
Have you tried the standard mersenne twister implementation? The following example is provided in Microsoft Online Help:
#include <random>
#include <iostream>
using namespace std;
int main()
{
random_device rd; // non-deterministic generator
mt19937 gen(rd()); // to seed mersenne twister.
uniform_int_distribution<> dist(0,10); // distribute results between 1 and 10 inclusive.
for (int i = 0; i < 5; ++i) {
cout << dist(gen) << " "; // pass the generator to the distribution.
}
cout << endl;
}
Last time I used an implementation from Makoto Matsumoto and it was faster than rand()
. I haven't tested it, but I would assume the standard implementation is faster as well.
SSE2 also has dedicated support for random number generation, which can be even faster: https://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4- processor
source to share