Mersenne Twister

Mersenne Twister è un algoritmo per la generazione di numeri pseudocasuali sviluppato nel 1997 da Makoto Matsumoto (松本 眞) e Takuji Nishimura (西村 拓士).
E' un algoritmo che genera un ottimo insieme di numeri pseudocasuali, supplendo a varie mancanze presenti negli altri algoritmi per generare numeri pseudocasuali oggi diffusi e usati (come il generatore LCG presente nel nucleo di base del C ( il famoso rand )).

Ci sono almeno due varianti conosciute di queste algoritmo, che differiscono solo nel valore del numero primo di Mersenne usato. Il più nuovo ed usato è il Mersenne Twister MT 19937.

Vantaggi

L'MT 19937 ha i seguenti vantaggi:

  1. E' stato progettato per avere una periodo a dir poco colossale: 219937 − 1 (i creatori di questo algoritmo hanno dimostrato questa proprietà). Questo perioro spiega l'origine del nome: è un Numero primo di Mersenne e alcune delle costanti dell'algoritmo sono anch'esse numeri primi di Mersenne.
  2. E' più veloce della maggior parte degli algoritmi di pari prestazioni qualitative.
  3. Ha passato numerosi test statistici di casualità, tra cui il test Diehard

Pseudocodice

Il seguente codice genera integer a 32 bit equidistribuiti nel range [0, 2^21-1] con l'algoritmo MT19937:

 // Crea una array lunga 624 interi per salvare lo stato del generatore
var int[0..623] MT
var int y
// Inizializza il generatore dato un seed (seme)
function initialiseGenerator ( 32-bit int seed ) {
MT[0] := seed
for i from 1 to 623 { // cicla su tutti gli elementi
MT[i] := last_32bits_of((69069 * MT[i-1]) + 1)
}
}

// genera una array di 624 numeri grezzi
function generateNumbers() {
for i from 0 to 622 {
y := 32nd_bit_of(MT[i]) + last_31bits_of(MT[i+1])
if y even {
MT[i] := MT[(i + 397) % 624] bitwise_xor (right_shift_by_1_bit(y))
} else if y odd {
MT[i] := MT[(i + 397) % 624] bitwise_xor (right_shift_by_1_bit(y)) bitwise_xor (2567483615)
}
}
y := 32nd_bit_of(MT[623]) + last_31bits_of(MT[0])
if y even {
MT[623] := MT[396] bitwise_xor (right_shift_by_1_bit(y))
} else if y odd {
MT[623] := MT[396] bitwise_xor (right_shift_by_1_bit(y)) bitwise_xor (2567483615)
}
}

// Estrae un numero grezzo pseudocasuale basato sull'i-esimo valore
function extractNumber(int i) {
y := MT[i]
y := y bitwise_xor (right_shift_by_11_bits(y))
y := y bitwise_xor (left_shift_by_7_bits(y) bitwise_and (2636928640))
y := y bitwise_xor (left_shift_by_15_bits(y) bitwise_and (4022730752))
y := y bitwise_xor (right_shift_by_18_bits(y))
return y
}
Comments