Generating random numbers with Lehmer RNGs

Taking a look at a quick and dirty little random number generator that's great for procedural generation.

The Lehmer RNG

A Lehmer RNG is a type of linear congruential generator (LCG) named after D. H. Miller.

This particular RNG is also sometimes called the Park-Miller RNG after Stephen K. Park and Keith W. Miller, who came up with the specific parameters for the calculation.

Lehmer RNGs are very easy to create, and they provide suitable random numbers for many applications (I use similar constructs whenever I need random values for world generation in game code). One nice benefit of the simplicity of the system is that these generators work great for procedural generation due to the usage of a seed value.

How the Lehmer RNG works

The math is very simple. First, we start by assigning some seed value.

Any time we want a random number, we use the following formula:

\[ seed_{n+1} = a * seed_{n}\text{ mod }m \]

To understand what \(a\) and \(m\) represent, I highly recommend reading through the wikipedia article linked at the bottom of this post¹.

The resulting value \(seed_{n+1}\) is both our random number and the input seed (\(seed_{n}\)) for the next random number. This is the linear part of the LCG.

Stephen K. Park and Keith W. Miller (after some revisions) proposed the following values for their Lehmar RNG:

• \(a\): 48,271
• \(m\): \(2^{31}-1\), or \(2,147,483,647\) (0x7FFFFFFF in hexadecimal)

One last note: the initial seed value, \(seed_{0}\) must be coprime with the selected values for \(m\)!

An Implementation in rust

The Lehmer RNG

Due to the simplicity of the Lehmer RNG, it's very easy to create one for use in your projects. In this example, I chose a seed arbitrarily (which means each time I run the program, the same values are generated).

/**
 * a Lehmer RNG using Park and Miller's parameters
 */
pub struct LehmerRandomNumberGenerator {
    seed: u32,
}

impl LehmerRandomNumberGenerator {
    // new LRNGs only need the seed value
    pub fn new(seed: u32) -> Self {
        Lcg { seed }
    }

    // getting the next random number is easy!
    // we apply the calculation to the current seed, then update
    //  the seed to that value.
    // finally, we return the current seed as the random value
    pub fn next_u32(&mut self) -> u32 {
        self.seed = (self.seed as u64 * 48271 % 0x7fff_ffff) as u32;
        self.seed
    }

    // getting a random float between 0 and 1 is easy too
    // we get the next random number, and divide by our maximum
    //  possible value
    pub fn next_f32(&mut self) -> f32 {
        self.next_u32() as f32 / 0x7fff_ffff as f32
    }
}

Using our Lehmer RNG

We'll write some code to test our RNG. We generate 100,000 random numbers, and track the highest and lowest values that we generate -- in this case using the next_f32() function which returns a floating point value between 0 and 1.

Hopefull the min and max values are close to 0 and 1 respectively!

fn main() {
    // create a LehmerRandomNumberGenerator
    // note that I've chosen to seed the RNG here with 0x45
    let mut lcg = LehmerRandomNumberGenerator::new(0x45);
    let mut max = 0.0;
    let mut min = 0x7fff_ffff as f32;

    // calculate the first 100,000 random numbers
    //  from the RNG and track max and min
    for _ in 1..100_000 {
        let x = lcg.next_f32();
        max = if x > max { x } else { max };
        min = if x < min { x } else { min };
    }

    println!("{}, {}", min, max);
}

Output:

$ cargo run
   Compiling rand v0.1.0 (C:\repos\sandbox\rand)
    Finished dev [unoptimized + debuginfo] target(s) in 0.67s
     Running `target\debug\rand.exe`
0.0000022319146, 0.9999807

That's well within acceptable range for use in game development!

---

1. More about Lehmer RNGs (wikipedia) ↩