Martin Andersson - 1 year ago 103

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 Source

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.