Mersennetwister
De mersennetwister is een pseudotoevalsgenerator ontwikkeld in 1997 door Makoto Matsumoto en Takuji Nishimura. Dit algoritme kan snel pseudowillekeurige getallen van zeer goede kwaliteit genereren, omdat het speciaal ontwikkeld is om gebreken van oudere algoritmes te vermijden.
Er zijn ten minste twee gebruikelijke varianten van het algoritme, die alleen verschillen in de grootte van de gebruikte mersennepriemgetallen. Het nieuwere en meer gebruikte algoritme is de mersennetwister MT 19937.
MT 19937 heeft de volgende gewenste eigenschappen:
- Het is ontworpen met een kolossale periode van 219937 − 1 (de ontwerpers van het algoritme hebben deze eigenschap bewezen). Deze periode verklaart de naam van het algoritme: het genoemde getal is een mersennepriemgetal en sommige garanties van het algoritme zijn afhankelijk van het interne gebruik van mersennepriemgetallen. In de praktijk is het nauwelijks nodig grotere priemgetallen te gebruiken.
- Het heeft een zeer hoge orde van dimensionale gelijkverdeling. Merk op dat dit per definitie betekent dat er een te verwaarlozen seriële correlatie is tussen opeenvolgende waarden van de uitvoerreeks.
- Het is sneller dan alle generatoren (met uitzondering van de statistisch gezien meest ondeugdelijke generatoren).
- Het is statistisch gezien willekeurig in alle bits van de uitvoer en doorstaat de strenge Diehard-testen.
Werking
bewerkenHet algoritme zelf is een ge'twist' gegeneraliseerd terugkoppelingsschuifregister. De "twist" is een transformatie die zorgt voor de gelijkverdeling van de gegenereerde getallen in 623 dimensies (lineaire congruentiegeneratoren kunnen op hun best een redelijke verdeling in vijf dimensies bewerkstelligen).
In tegenstelling tot de Blum-Blum-Shubgenerator, is het algoritme in zijn oorspronkelijke vorm niet geschikt voor cryptografie. Voor veel andere toepassingen is het daarentegen snel de standaard toevalsgenerator aan het worden.
Referentie
bewerken- M. Matsumoto en T. Nishimura, Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator, ACM Trans. on Modeling and Computer Simulations, 1998.