The Mersenne Twister is a widely used pseudorandom number generator (PRNG) known for its fast generation and high-quality randomness. Developed by Makoto Matsumoto and Takuji Nishimura, 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.
In this article, we explore the implementation of a Mersenne Twister generator in Rust, covering the algorithm, implementation details, and usage examples! 🦀
Concepts Behind the Mersenne Twister
The Mersenne Twister is a pseudorandom number generator (PRNG) widely used because of its long period and high quality of randomness. The key idea is to produce a sequence of numbers that appear random and are suitable for use in simulations, games, and other applications.
Key Characteristics
- 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.
- State Vector: The generator maintains a state vector of 624 32-bit words, which it uses to generate random numbers.
- Tempering: The generator output is further processed to improve the distribution of values.
Mersenne Twister Algorithm
Key Features
- Period: 2^19937 — 1
- Word Size: 32 bits
- State Size: 624 words (19968 bits)
- Initialization: Seed value
Algorithm Steps
- Initialization: The generator is initialized with a seed value to set the initial state.
- Twist Transformation: Periodically, the state vector is transformed to ensure randomness properties.
- Generation of Random Numbers: The generator produces a random 32-bit integer at each step.
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
Implementing the Mersenne Twister in Rust
Step 1: Define the Mersenne Twister Struct
First, we define a struct to hold the state of the generator.
const N: usize = 624;
const M: usize = 397;
const MATRIX_A: u32 = 0x9908B0DF;
const UPPER_MASK: u32 = 0x80000000;
const LOWER_MASK: u32 = 0x7FFFFFFF;
struct MersenneTwister {
mt: [u32; N],
index: usize,
}
impl MersenneTwister {
fn new(seed: u32) -> Self {
let mut mt = [0u32; N];
let mut twister = MersenneTwister { mt, index: N + 1 };
twister.initialize(seed);
twister
}
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);
}
}
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;
}
}
}
fn extract_number(&mut self) -> u32 {
if self.index >= N {
if self.index > N {
panic!("Generator was never seeded");
}
self.generate_numbers();
self.index = 0;
}
let mut y = self.mt[self.index];
self.index += 1;
y ^= (y >> 11);
y ^= (y << 7) & 0x9D2C5680;
y ^= (y << 15) & 0xEFC60000;
y ^= (y >> 18);
y
}
}
Step 2: Initialization
The initialization function sets the initial state of the generator using a given seed value.
impl MersenneTwister {
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);
}
}
}
Step 3: Twist Transformation
The generate_numbers function performs the twist transformation to generate new values in the state array.
impl MersenneTwister {
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;
}
}
}
}
Step 4: Extracting Random Numbers
The extract_number function returns a random 32-bit integer and applies tempering to improve the distribution of the output values.
impl MersenneTwister {
fn extract_number(&mut self) -> u32 {
if self.index >= N {
if self.index > N {
panic!("Generator was never seeded");
}
self.generate_numbers();
self.index = 0;
}
let mut y = self.mt[self.index];
self.index += 1;
y ^= (y >> 11);
y ^= (y << 7) & 0x9D2C5680;
y ^= (y << 15) & 0xEFC60000;
y ^= (y >> 18);
y
}
}
Step 5: Usage Example
Here’s how you can use the MersenneTwister struct to generate random numbers.
fn main() {
let mut rng = MersenneTwister::new(5489);
for _ in 0..10 {
println!("{}", rng.extract_number());
}
}
Full Implementation
Here is the complete code for the Mersenne Twister implementation in Rust:
const N: usize = 624;
const M: usize = 397;
const MATRIX_A: u32 = 0x9908B0DF;
const UPPER_MASK: u32 = 0x80000000;
const LOWER_MASK: u32 = 0x7FFFFFFF;
struct MersenneTwister {
mt: [u32; N],
index: usize,
}
impl MersenneTwister {
fn new(seed: u32) -> Self {
let mut mt = [0u32; N];
let mut twister = MersenneTwister { mt, index: N + 1 };
twister.initialize(seed);
twister
}
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);
}
}
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;
}
}
}
