Mersenne Twister PRNG in Rust

This is a Rust implementation of the Mersenne Twister (MT19937) pseudorandom number generator (PRNG). This implementation allows you to generate random numbers seeded with the process ID (PID) of the running program, making the sequence of generated numbers different each time the program is run.

The official Research Paper of Mersenne Twister: Mersenne twister (acm.org)

---

Mersenne Twister

The Mersenne Twister is a widely used pseudorandom number generator (PRNG) known for its fast generation and high-quality randomness. It produces a sequence of 32-bit integers with a very long period of 2^19937−1 and a high degree of uniformity and independence among the values.

At its core, the Mersenne Twister utilizes a matrix operation known as matrix multiplication to generate its pseudorandom sequences. This process involves shifting, masking, and XOR operations on the generated numbers to produce the final output. The algorithm also employs a large state space, usually comprising a 624-element array, which is repeatedly transformed to produce new random numbers. This state space and the algorithm’s structure allow it to generate a vast number of random sequences before repeating, providing a long period of randomness.

Key Characteristics

1. Period: The Mersenne Twister has an exceptionally long period of 2^19937 — 1. This means it will generate a very long sequence of random numbers before repeating.

2. State Vector: The algorithm uses an internal state vector (mt) of 624 32-bit unsigned integers, which is updated on every iteration to generate new numbers. The size of this vector is critical to the algorithm's ability to produce a long period and high-quality randomness.

3. Twisting Transformation: The core of the Mersenne Twister algorithm involves a "twist" transformation that mixes the bits of the state vector to ensure that the output has good statistical properties. This transformation combines the upper and lower bits of the state vector in a way that depends on the constants MATRIX_A, UPPER_MASK, and LOWER_MASK.

4. Tempering: After generating numbers from the state vector, the algorithm applies a tempering transformation to improve the distribution of the output. This involves a series of bitwise shifts and XOR operations that reduce potential correlations between generated numbers.

Key Features

• Period: 2^19937 — 1
• Word Size: 32 bits
• State Size: 624 words (19968 bits)
• Initialization: Seed value

Key Properties

• Period: The period of MT19937 is 219937−1, meaning it can generate this many numbers before the sequence starts repeating. This long period is one of the reasons why MT19937 is widely used in simulations and applications requiring high-quality random numbers.

• Uniform Distribution: The numbers generated by the Mersenne Twister are uniformly distributed across the possible range of 32-bit unsigned integers.

• Efficiency: The algorithm is highly efficient, requiring minimal computational overhead to generate each random number.

Parameters

The Mersenne Twister uses several parameters for its internal operations:

• w: Word size (32 bits)
• n: Degree of recurrence (624)
• m: Middle word, offset (397)
• r: Separation point of one word (31)
• a: Coefficient of the rational normal form twist matrix
• u, d, s, b, t, c, l: Bitwise masks and shifts

Algorithm Overview

Tempering

Steps of Algorithm

---

Code Overview

const N: usize = 624;
const M: usize = 397;
const MATRIX_A: u32 = 0x9908B0DF;
const UPPER_MASK: u32 = 0x80000000;
const LOWER_MASK: u32 = 0x7FFFFFFF;

• N: The size of the state vector mt, which is 624 for MT19937.
• M: A parameter used in the twist transformation, set to 397.
• MATRIX_A: A constant used in the twist transformation, defined as 0x9908B0DF.
• UPPER_MASK and LOWER_MASK: These masks are used to split a 32-bit integer into its upper and lower bits during the generation of new numbers

Struct: MersenneTwister

struct MersenneTwister {
    mt: [u32; N],
    index: usize,
}

• mt: This is an array that holds the state of the generator. It has a size of N (624).
• index: This keeps track of the position within the array mt. It starts at N + 1 to indicate that numbers need to be generated before extraction.

Implementing MersenneTwister

impl MersenneTwister {
    fn new(seed: u32) -> Self {
        let mut mt = [0u32; N];
        let mut twister = MersenneTwister { mt, index: N + 1 };
        twister.initialize(seed);
        twister.index = N;
        twister
    }

• new(seed: u32) -> Self: This function is a constructor for creating a new instance of the Mersenne Twister PRNG. It initializes the mt array and sets the index to N after calling the initialize function with the provided seed.

initialize Function

fn initialize(&mut self, seed: u32) {
    self.mt[0] = seed;
    for i in 1..N {
        self.mt[i] = (1812433253u32)
            .wrapping_mul(self.mt[i - 1] ^ (self.mt[i - 1] >> 30))
            .wrapping_add(i as u32);
    }
}

• initialize(&mut self, seed: u32): This function initializes the state vector mt with the given seed. It sets the first element of mt to the seed, and each subsequent element is generated from the previous one using a specific formula.

generate_numbers Function

fn generate_numbers(&mut self) {
    for i in 0..N {
        let y = (self.mt[i] & UPPER_MASK) | (self.mt[(i + 1) % N] & LOWER_MASK);
        self.mt[i] = self.mt[(i + M) % N] ^ (y >> 1);
        if y % 2 != 0 {
            self.mt[i] ^= MATRIX_A;
        }
    }
}

• generate_numbers(&mut self): This function generates N new random numbers by transforming the state vector mt. The transformation involves combining elements of mt, applying shifts, and mixing bits with the MATRIX_A constant.

extract_number Function

fn extract_number(&mut self) -> Result<u32, &'static str> {
        if self.index >= N {
            if self.index > N {
                panic!("Generator was never seeded");
            }
            self.generate_numbers();
            self.index = 0;
        }

        // Tempering Process
        let mut y = self.mt[self.index];
        self.index += 1;
        y ^= (y >> 11);
        y ^= (y << 7) & 0x9D2C5680;
        y ^= (y << 15) & 0xEFC60000;
        y ^= (y >> 18);
        Ok(y)
    }

• extract_number(&mut self) -> Result<u32, &'static str>: This function extracts and returns a random number from the state vector. If necessary, it regenerates the numbers by calling generate_numbers. The extracted number is then tempered using a series of bitwise operations to improve its distribution. It returns a Result<T, E>. It helps us to check and handle errors in a better way.

Main Function

fn main() {
    let pid = process::id() as u32;
    let mut rng = MersenneTwister::new(pid);
    for i in 0..20 {
        match rng.extract_number() {
            Ok(num) => println!("PRNG {} = {}", i+1, num),
            Err(e) => eprintln!("Error:{}", e),
        }
    }
}

• main(): The entry point of the program. It seeds the Mersenne Twister with the process ID (pid) of the running program and then extracts and prints 20 random numbers. It matches the patter of the return value with the outputs of the Result<T,E>. If everything is fine then Ok(num) works else Error is printed.

---

Tempering Process

The tempering process in the Mersenne Twister algorithm is a final transformation applied to the generated number before it is returned as the output. This process improves the statistical properties of the generated numbers, making them appear more uniformly distributed and reducing any detectable patterns or correlations.

The tempering process involves a series of bitwise operations (shifts and XORs) on the 32-bit integer y. The specific constants and bitwise operations were chosen empirically to improve the distribution of the output values.

1. Initial Value

   let mut y = self.mt[self.index];

   • This initializes y with the current state value from the state vector.

2. First Tempering Operation

   y ^= (y >> 11);

   • Operation: y is XORed with itself right-shifted by 11 bits.
   • Effect: This mixes the higher bits into the lower bits, spreading the information across the bits.

3. Second Tempering Operation

   y ^= (y << 7) & 0x9D2C5680;

   • Operation: y is XORed with itself left-shifted by 7 bits, masked with 0x9D2C5680.
   • Effect: This operation further mixes the bits, especially targeting the middle bits due to the specific bitmask.

4. Third Tempering Operations

   y ^= (y << 15) & 0xEFC60000;

   • Operation: y is XORed with itself left-shifted by 15 bits, masked with 0xEFC60000.
   • Effect: This operation mixes the upper bits, spreading information from the upper part of the number into other parts.

5. Fourth Tempering Operation

   y ^= (y >> 18);

   • Operation: y is XORed with itself right-shifted by 18 bits.
   • Effect: This final mixing operation spreads the information further, ensuring that the bits are well-mixed.

Understanding the Masks

In the context of the Mersenne Twister algorithm, the masks are applied during the tempering process to selectively modify certain bits of the intermediate value y. The masks used are:

• 0x9D2C5680: This hexadecimal constant corresponds to the 32-bit binary value 10011101001011000101011010000000.
• 0xEFC60000: This hexadecimal constant corresponds to the 32-bit binary value 11101111110001100000000000000000.

These masks are used in conjunction with bitwise AND operations to selectively influence the bits at specific positions.

---

How to Run

1. Ensure you have Rust installed on your machine.

2. Copy the code into a .rs file, for example, mersenne_twister.rs.

3. Compile the code using Cargo or Rust's rustc compiler

   rustc mersenne_twister.rs

4. Run the compiled binary

   ./mersenne_twister 

   Or

   mersenne_twister.exe

---