Need a fast random generator for c++

Question

Hi guys.

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

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 2

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

Answer 3

The Mersenne Twister has some fast implementations.

Answer 4

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.

Answer 5

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 6

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 7

Two good alternatives from intel's site:

1) fastrand - it is 2.01 X faster then 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/