Need a fast random generator for c++

Question

I'm trying to do some opt-3 swapping on my TSP generator for euclidian distances, and since I in many cases have more than ~500 nodes, I need to randomly select at least 1 of the 3 nodes that I want to try swapping.

So basically I need a random-number function that's fast. (the normal rand() is way too slow) It doesn't have to be awesome, just good enough.

EDIT: I forgot to mention, i'm sitting at an environment where I can't add any libraries except the Standard Language Library (such as STL, iostream etc). So no boost =/

Answer 1

The other thread mentioned Marsaglia's xorshf generator, but no one posted the code.

static unsigned long x=123456789, y=362436069, z=521288629;

unsigned long xorshf96(void) {          //period 2^96-1
unsigned long t;
    x ^= x << 16;
    x ^= x >> 5;
    x ^= x << 1;

   t = x;
   x = y;
   y = z;
   z = t ^ x ^ y;

  return z;
}

I've used this one all over the place. The only place it failed was when I was trying to produce random binary matrices. Past about 95x95 matrices, it starts generating too few or too many singular matrices (I forget which). It's been shown that this generator is equivalent to a linear shift feedback register. But unless you are doing cryptography or serious monte carlo work, this generator rocks.

Answer 2

Two good alternatives from intel's site:

1) fastrand - it is 2.01 X faster than the std rand(). The routine returns one integer, similar output value range as C lib.

inline int fastrand() { 
  g_seed = (214013*g_seed+2531011); 
  return (g_seed>>16)&0x7FFF; 
} 

2) an SSE version (see link below) is about 5.5 X as fast as std rand() however it generates 4 random values at a time, requires a processer with sse (almost all do), and is more complicated.

http://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/

Answer 3

See these generators from random number generator expert George Marsaglia. They're implemented as C macros, and they're lightning fast, just a few operations per number generated.

Answer 4

Starting with Ivy Bridge architecture Intel added RdRand CPU instruction and AMD added it later in June 2015. So if you are targeting a processor that is new enough and don't mind using (inline) assembly, the fastest way to generate random numbers should be in calling RdRand CPU instruction to get a 16- or 32- or 64-bit random number as described here. Scroll to approximately the middle of the page for code examples. At that link there is also a code example for checking the current CPU for support of RdRand instruction, and see also the Wikipedia for an explanation of how to do this with the CPUID instruction.

Related question: Making use of sandy bridge's hardware true random number generator? (though according to Wikipedia, RdRand instruction first appeared in Ivy Bridge, but not Sandy Bridge architecture as that question says)

Example C++ code based on _rdrand64_step() :

#include <immintrin.h>

uint64_t randVal;
if(!_rdrand64_step(&randVal)) {
  // Report an error here: random number generation has failed!
}
// If no error occured, randVal contains a random 64-bit number

Answer 5

The Mersenne Twister has some fast implementations.

Answer 6

Even tho this post is years old, it showed up when I was looking for a similar answer, and the answer I wound up using, isnt even in it. So I'm adding the one I found;

#include <random> msdn entry

This approach will build a self contained random generator, and I found it to be a lot more random than rand()%x; over a few hundred thousand iterations. rand()% would never throw 16+ heads/tails in a row, when it should every other 65k attempts. This one not only does that, but it does it in a quarter of the time.

This is how I implement #include <random> myself:

//create rng_gen, using mt technique, with range 0,1 (coin) and 1,6(dice);
std::random_device rd; //seed
std::mt19937 gen(rd()); //seed for rd(Mersenne twister)
std::uniform_int_distribution<> rng_coin(0, 1); //rng1 range
std::uniform_int_distribution<> rng_dice(1, 6); ///rng2 range

rng_coin(gen); //will apply rng1 range on (gen) object. Is very fast
rng_dice(gen); //will apply rng2 range, returns int.

//will output 1000 cointosses to console
for (int i=0;i<1000;++i)std::cout<<rng_coin(gen)<<"\n";
//will generate 1000 dice throws
for (int i=0;i<1000;++i)rng_dice(gen);

Answer 7

Boost library has a set of random generators. Performance chart could be found here.

EDIT: This answer was here before the edit of the original question. But I hope it could be still helpful, so I leave it here.

Answer 8

can you pregenerate a bunch of random bits ahead of time and peel them off 2 at a time (since you only need a random number between 1 and 3)?

Answer 9

I think WELL is pretty good, and WELL512a is pretty short. http://www.iro.umontreal.ca/~panneton/WELLRNG.html WELL44497a is complex at the time too. However, WELL generates a number between 0 and 1.

Answer 10

rand() is really darn fast, and I don't believe you'll find much faster.

If it is in fact slowing you down (which I kinda doubt), then you need an architecture change.

I recommend pre-populating a long list with random numbers, then when you need one, simply take one from the list, rather than generating one. You may be able to re-fill the list with a background thread.