[ACCEPTED]-Fast pseudo random number generator for procedural content-random

Seems like you're asking for a hash-function 8 rather than a PRNG. Googling 'fast hash 7 function' yields several promising-looking 6 results.

For example:

uint32_t hash( uint32_t a)
    a = (a ^ 61) ^ (a >> 16);
    a = a + (a << 3);
    a = a ^ (a >> 4);
    a = a * 0x27d4eb2d;
    a = a ^ (a >> 15);
    return a;
}

Edit: Yep, some hash functions definitely 5 look more suitable than others.

For your 4 purposes, it should be sufficient to eyeball 3 thefunction and check that a single-bit 2 change in the input will propagate to lots 1 of output bits.

Yep, you are looking for a fast integer 5 hash algorithm rather than a PRNG.

This page has 4 a few algorithms, I'm sure you'll find plenty 3 more now you know the correct search terms.

Edit: The 2 original page has been removed, a live version 1 can be found on GitHub.

Here's a small random number generator developed 8 by George Marsaglia. He's an expert in 7 the field, so you can be confident the generator 6 has good statistical properties.

v = 36969*(v & 65535) + (v >> 16);
u = 18000*(u & 65535) + (u >> 16);
return (v << 16) + (u & 65535);

Here u and 5 v are unsigned ints. Initialize them to 4 any non-zero values. Each time you generate 3 a random number, store u and v somewhere. You 2 could wrap this in a function to match your 1 signature above (except the ints are unsigned.)

see std::tr1::ranlux3, or other random number generators 12 that are part of TR1 additions to the standard 11 C++ library. I suggested mt19937 initialially, but 10 then saw your note that it needs to be very 9 fast. TR1 is should be available on Microsoft VC++ and 8 GCC, and can also be found in the boost 7 libraries which support even more compilers.

example 6 adapted from boost documentation:

#include <random>
#include <iostream>
#include <iterator>
#include <functional>
#include <algorithm>
#include <ctime>
using namespace std;
using namespace std::tr1;
int main(){
    random_device trueRand;
    ranlux3 rng(trueRand);  // produces randomness out of thin air
                            // see pseudo-random number generators
    uniform_int<> six(1,6); // distribution that maps to 1..6
                            // see random number distributions
    variate_generator<ranlux3&, uniform_int<> >
           die(rng, six);   // glues randomness with mapping

    // simulate rolling a die
    generate_n( ostream_iterator<int>(cout, " "), 10, ref(die));
}

example output:

2 4 4 2 4 5 4 3 6 2

Any TR1 random 5 number generator can seed any other random number 4 generator. If you need higher quality results, consider 3 feeding the output of mt19937 (which is 2 slower, but higher quality) into a minstd_rand 1 or randlux3, which are faster generators.

If memory is not really an issue and speed 11 is of utmost importance then you can prebuild 10 a large array of random numbers and just 9 iterate through it at runtime. For example 8 have a seperate program generate 100,000 7 random numbers and save it as it's own file 6 like

unsigned int randarray []={1,2,3,....}

then 5 include that file into your compile and 4 at runtime your random number function only 3 needs to pull numbers from that array and 2 loop back to the start when it hits the 1 end.

I use the following code in my Java random 3 number library - this has worked pretty 2 well for me. I also use this for generating 1 procedural content.

/**
 * 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 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;
}