Need a fast random generator for c++ [closed]

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

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 2

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 3

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 4

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 5

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 6

The Mersenne Twister has some fast implementations.