Source

## What makes RNG “good”? §

• Fair statistical distribution
• Low degree of repetition (more correct: a statistically correct degree of repetition)
• High theoretical maximum (best-case) repeat period
• High guaranteed minimum (worst-case) repeat period: crucially should be about ~million-billion range
• Seedable with a nice range of seeds: we don’t want seeds that limit us to only odd numbers or only large primes
• Fast warm up: some popular RNGs have pretty terrible initial values!
• Platform independence: behaviour should be consistent across platforms
• Deterministic: the same seed should lead to the same results
• Speed: we may want to be able to generate lots of numbers, fast!
• Parallelism: is it thread safe?

Why not use rand()?

• Only gives us 15-bits of random numbers (range is )
• Not very fast!
• Not very good, statistically speaking

## What RNG should we use? §

### Lehmer/Park-Miller §

1. Scale by prime S
2. Modulus by prime M
uint32_t m_state = 1337; // initial seed
uint32_t S = 0x0000BC8F;
uint32_t M = 0x7FFFFFF;
uint32_t LcgParkMiller::Rand() {
m_state = (m_state * S) % M;
return m_state;
}

Problem: can get stuck at 0 if the seed is bad

### MCGs (Mixed Congruential Generator) §

1. Scale by prime S
2. Add bias B
3. Modulus by prime M
uint32_t m_state = 1337; // initial seed
uint32_t S = 0x0019660D;
uint32_t M = 0x3C6EF35F;
uint32_t M = 0x7FFFFFF;
uint32_t LcgParkMiller::Rand() {
m_state = (m_state * S + B) % M;
return m_state;
}

### Xor shifting §

1. Bit-shift around and xor with yourself a few times
uint32_t m_state = 1337; // initial seed
uint32_t xorshift1::Rand() {
m_state ^= (m_state << 13);
m_state ^= (m_state >> 17);
m_state ^= (m_state << 5);
return m_state;
}

### Noise functions §

• Order independent RNG!
• Infinite table: put an index in, get a random float or number back out
• 1-D function: index is a single number
• 2-D function: index is a pair of numbers
• N-D function: index is an n-tuple
• Totally pure: noise = mungeAndMangleBits(position)
• Can actually use hash functions for this
• crc32, Murmur , Squirrel3, and std::hash are all very good and fast
• md5 and sha1 are good but slow (cryptographically sound)

### n-D noise from 1D noise function §

Basically munge the coordinates together my multiplying by a large prime number with non-boring bits. Be careful to make sure that the primes are magnitudes apart!

uint32_t Get3DNoise(int x, int y, int z, uint32_t seed) {
constexpr int PRIME1 = 198491317;
constexpr int PRIME2 = 6542989;
return Get1DNoise(x + (PRIME1 * y) + (PRIME2 * z), seed);
}