Mersenne Twister
|
URI: |
http://herbert.gandraxa.com/herbert/rng.asp |
|
Link template: |
<a href="http://herbert.gandraxa.com/herbert/rng.asp">Mersenne Twister</a> |
|
Link symbols: |
|
On current page |
ZIP archive |
PDF |
E-Mail
Article
Organization
Home »
Linoleum Source Code » Mersenne Twister
- Source Code Library: The implementation in the cross-platform Assembler Linoleum.
- Source Code Test Program: Test program using the library.
Download as a WinZip file see below.
Scope
This implements the Mersenne Twister 19937 in the 
Linoleum Programming Language.
The Mersenne Twister 19939 (commonly referred to as "MT19937") is a pseudorandom number generator developed in 1997 by Makoto Matsumoto and Takuji Nishimura.
It provides for fast generation of very high quality pseudorandom numbers, having been designed specifically to rectify many of the flaws found in older algorithms.
There are at least two common variants of the algorithm, differing only in the size of the Mersenne primes used. The newer and more commonly used one is MT19937, which is the one implemented here.
Algorithm Development Update: In August 2006 a new version was released, named "SIMD-oriented Fast Mersenne Twister (SFMT)" (commonly referred to as SFMT19937). Quote from the developers' 
annoucement:
SFMT is a Linear Feedbacked Shift Register (LFSR) generator that generates a 128-bit pseudorandom integer at one step. SFMT is designed with recent parallelism of modern CPUs, such as multi-stage pipelining and SIMD (e.g. 128-bit integer) instructions.
For details see the External Pages section.
Author
Published
2006-May-30
External Pages
- Find a good overwiew of Pseudo Random Number Generators (PRNGs) in general in the Dictionary of Algorithms and Data Structures, from Paul E. Black (NIST)
- Mersenne Twister
- The technical paper [PDF] describing the algorithm, by Makoto Matsumoto, also has the Original C ++ code
- Working implementations in different languages see listing at the University of Hiroshima
- Should cryptographic usage be required, see Cryptographic MT and Fubuki Stream/Block Cipher [PDF], by Makoto Matsumoto, Takuji Nishimura, Mariko Hagita and Mutsuo Saito
- For details about the new SFMT19937 see Design and Implementation of 128-bit Instruction-Based Fast PRNG from Mutsuo Saito.
Download
The following ZIP file contains both the library's source (RNG.txt) as well as a test program (RNG Test.txt).
Note: For naming convention reasons my libraries all begin with a 3-characters prefix; RNG (Random Number Generator) was the natural choice for this library. Despite its naming, though, this is a Pseudo Random Number Generator. Thanks to Paul E. Black (NIST) to pointing out this potentially irritating naming of mine.
Test
The implementation was tested with the first 1,000 output numbers provided by the developers of the algorithm.
Speed
PRNs = Pseudo Random Numbers
| Machine | Measured | Interpolated per second |
| Intel Pentium 4, 1.328 GHz | 500 million PRNs in 17 seconds | 29.4 million PRNs/second |
| Intel Celeron D 346, 3.066 GHz | 2 billion PRNs in 28 seconds | 71.4 million PRNs/second |
Note: There is plenty of room for speed optimization. The current implementation focusses on correctness.
