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;
}
}
}
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;
}
// 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);
y
}
}
fn main() {
let mut rng = MersenneTwister::new(5489);
for _ in 0..10 {
println!("{}", rng.extract_number());
}
}
The 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.
Let’s break down each step of the tempering process:
