Cheap and cheerful rand() replacement.

Question

After profiling a large game playing program, I have found that the library function rand() is consuming a considerable fraction of the total processing time. My requirements for the random number generator are not very onerous - its not important that it pass a great battery of statistical tests of pure randomness. I just want something cheap and cheerful that is very fast. Any suggestions?

Answer 1

You are probably looking for a linear congruential generator.

Answer 2

You can use some pre-calculated values for random numbers and store them in some arrays. The RNG algorithms are not a very easy task to do. If you need just a small amount of random numbers then this is a solution in my opinion.

Usually in games there is a lot of pre-calculation (sin/cos values and other stuff that is used very often inside a video game and it would consume a lot of CPU cycles if not pre-calculated).

You can also look at HW RNG but I believe this is out of the question.

Answer 3

There are few algorithms in common use that are faster than an LCG (which is very, very likely what rand() is using). You may want to try Marsaglia's Xorshift generator which is pretty fast (depending on the hardware). The WELL512a generator is also quite fast (more so than MT19937 or MT19937-64).

Answer 4

This may not be a great answer, and is really more of a question.

Depending on the platform and the frequency of depending on the value, wouldn't the least significant numbers of a microsecond returning function approximate something 'random'?

Answer 5

The Mersenne Twister is said to be faster than many RAND implementations, but YMMV depending on implementation details and hardware.

Answer 6

Since you didn't say much about your implementation, if this is multithreaded using a function that uses a global state is almost always a bad idea. Many implementations then just use mutexes to protect concurrent access. The long times that you would observe then would just be waiting times and not the computation of the rand function itself. POSIX has the rand48 family of functions that also have reentrant versions that should do better on concurrent access, see http://opengroup.org/onlinepubs/007908799/xsh/drand48.html

Answer 7

Here's one I wrote for Java based on Marsaglia's XORShift algorithm that you could probably adapt. Works beautifully for my purposes (game development, simulation).

/**
 * State for random number generation
 */
private static volatile long state=xorShift64(System.nanoTime()|0xCAFEBABE);

/**
 * Gets a long random value
 * @return Random long value based on static state
 */
public static final long nextLong() {
    long a=state;
    state = xorShift64(a);
    return a;
}

/**
 * XORShift algorithm - credit to George Marsaglia!
 * @param a Initial state
 * @return new state
 */
public static final long xorShift64(long a) {
    a ^= (a << 21);
    a ^= (a >>> 35);
    a ^= (a << 4);
    return a;
}