gakushin logo
SFMT logo

SIMD-oriented Fast Mersenne Twister (SFMT):
twice faster than Mersenne Twister*1.

Japanese Version

News

LINK

What is SFMT?

SFMT is a new variant of Mersenne Twister (MT) introduced by Mutsuo Saito and Makoto Matsumoto in 2006. The algorithm was reported at MCQMC 2006. The article published in the proceedings of MCQMC2006. (see Prof. Matsumoto's Papers on random number generation.) 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. It supports 32-bit and 64-bit integers, as well as double precision floating point as output.

SFMT is much faster than MT, in most platforms. Not only the speed, but also the dimensions of equidistributions at v-bit precision are improved. In addition, recovery from 0-excess initial state is much faster. See Master's Thesis of Mutsuo Saito for detail.

The following implementation SFMT19937 can be compiled in three possible platforms:

  1. Standard C without SIMD instructions
  2. CPUs with Intel's SSE2 instructions + C compiler which supports these feature
  3. CPUs with PowerPC's AltiVec instructions + C compiler which supports these feature

In each platform, SFMT has better performance than MT: see comparison of speed.

We put tables of equidistribution of SFMT. They are 32bit and 64bit.

Download SFMT which supports various periods from 2607-1 to 2216091-1

This code is released on January 31st in 2007, so it may contain some bugs. Any feedback is welcome (send an email to Mutsuo Saito, saito "at sign" math.sci.hiroshima-u.ac.jp and m-mat "at sign" math.sci.hiroshima-u.ac.jp)

versionarchivechanges
new! 1.5.1 SFMT-src-1.5.1.zip
SFMT-src-1.5.1.tar.gz
fix potiential bug in period certification and SFMT-common.h include guard, reported by Kouhei Saitou. (2017/2/22)
1.5 SFMT-src-1.5.zip
SFMT-src-1.5.tar.gz
fix bug double precision output function sfmt_res53 reported by Akio Takahashi. It should return a nunmber in the range [0, 1), but sometime it returned 1.0. (2017/2/7)
1.4.1 SFMT-src-1.4.1.zip
SFMT-src-1.4.1.tar.gz
fix MSC compile error reported by Dirk Steenpass. (2013/12/19)
1.4 SFMT-src-1.4.zip
SFMT-src-1.4.tar.gz
internal state of SFMT is kept in structure. function and macro names are changed to have sfmt_ prefix. This version can work with SFMT-jump. ALTIVEC OR BIGENDIAN ARE NOT TESTED AT ALL. (2012/6/28)
1.3.3 SFMT-src-1.3.3.zip
SFMT-src-1.3.3.tar.gz
change not to compile do_recursion function when SSE2 or ALTIVEC is specified. This is to avoid compiler warning. (2007/10/6)
1.3.2 SFMT-src-1.3.2.zip
SFMT-src-1.3.2.tar.gz
Fix bug about to_res53_mix() and genrand_res53_mix(). (2007/8/20)
1.3.1 SFMT-src-1.3.1.zip
SFMT-src-1.3.1.tar.gz
Fix bug about compile error in MSC. Add two functions to_res53_mix() and genrand_res53_mix(). Change optimization option of gcc from -O9 to -O3. Add MSC __forceinline option. (2007/8/12)
1.3 SFMT-src-1.3.zip
SFMT-src-1.3.tar.gz
Add support for the period 2216091-1. BUG fixed about BIG ENDIAN. Add parameter data for parallel generation. Support AltiVec on OSs which are not osx. (2007/6/2)
1.2 SFMT-src-1.2.zip
SFMT-src-1.2.tar.gz
Now, various periods form 2607-1 to 2132049-1 are supported. The source code is combined. The second argument of vec_perm function is casted. (2007/3/1)
1.1 sfmt19937src-1.1.zip
sfmt19937src-1.1.tar.gz
The period certification method is changed from constant to function. Makefile and documents changed. (2007/1/31)
1.0 sfmt19937src-1.0.zip
sfmt19937src-1.0.tar.gz
First version.

If you have some trouble to download, try this page.

Double precision SIMD-oriented Fast Mersenne Twister (dSFMT)

The purpose of dSFMT is to speed up the generation by avoiding the expensive conversion of integer to double (floating point). dSFMT directly generates double precision floating point pseudorandom numbers which have the IEEE Standard for Binary Floating-Point Arithmetic (ANSI/IEEE Std 754-1985) format. dSFMT is only available on the CPUs which use IEEE 754 format double precision floating point numbers.

dSFMT doesn't support integer outputs. dSFMT supports the output of double precision floating point pseudorandom numbers which distribute in the range of [1, 2), [0, 1), (0, 1] and (0, 1). And it also supports the various periods form 2607-1 to 2132049-1. (dSFMT ver. 2.1 supports the periods from 2521-1 to 2216091-1.)

This code is released on March 12th in 2007, so it may contain some bugs. Any feedback is welcome (send an email to Mutsuo Saito, saito "at sign" math.sci.hiroshima-u.ac.jp and m-mat "at sign" math.sci.hiroshima-u.ac.jp)

The algorithm was reported at MCQMC 2008. This is the slide PDF file we used for the talk.
The article published in the proceedings of MCQMC2008. (see Prof. Matsumoto's Papers on random number generation.)

versionarchivechanges
new! 2.2.3 dSFMT-src-2.2.3.zip
dSFMT-src-2.2.3.tar.gz
change Makefile for nmake. (2013/12/19)
2.2.2 dSFMT-src-2.2.2.zip
dSFMT-src-2.2.2.tar.gz
Fix compile error on Visual C++ 2012. (2013/9/17)
2.2.1 dSFMT-src-2.2.1.zip
dSFMT-src-2.2.1.tar.gz
Definitions of Shift constant in AltiVec were changed. They had not been fit to the instruction set architecture of AltiVec. (2013/2/21)
2.2 dSFMT-src-2.2.zip
dSFMT-src-2.2.tar.gz
The initialization of the constants for sse2 is changed. dSFMT-common.h is created. This version can work with dSFMT Jump function. (2012/6/29)
2.1 dSFMT-src-2.1.zip
dSFMT-src-2.1.tar.gz
This version supports the periods from 2521-1 to 2216091-1. We added new function dsfmt_genrand_uint32, which returns 32-bit unsigned integer. If you need many floating point pseudo random numbers and a few integers, you don't need to use another integer generator. (2009/4/18)
2.0 dSFMT-src-2.0.zip
dSFMT-src-2.0.tar.gz
The recursion formula of dSFMT is changed. The supported periods are changed. The output sequences are completely changed. The generation speed is improved. The variable for initialization check is removed, because it causes an execution error in cygwin. dSFMT ver. 2.0 supports the periods from 2521-1 to 219937-1 currently. dSFMT ver. 2.0 is developed for higher speed. No serious problems are reported for dSFMT ver. 1.xx. (2008/8/26)
1.3 dSFMT-src-1.3.zip
dSFMT-src-1.3.tar.gz
use structure of C language. bug fix about checking BIG_ENDIAN. Function names are changed to have the prefix dsfmt_, but old names are also available. (2008/2/28)
1.2.1 dSFMT-src-1.2.1.zip
dSFMT-src-1.2.1.tar.gz
add #include <altivec.h> to dSFMT.c. (2007/8/29)
1.2 dSFMT-src-1.2.zip
dSFMT-src-1.2.tar.gz
CAUTION: dSFMT.xxx.out.txt is changed. Bug fixed in test.c about printf precision specifier. Larger period 2216091-1 is supported. gcc compile option changed form -O9 to -O3. Add AltiVec parameter format for systems which are not OSX. Change Makefile for systems which are not OSX and support AltiVec. Change sample2 of howto-compile for Free BSD. Change period certification code more smart. Change source files for BORLANDC and Visual Studio. (2007/8/22)
1.1 dSFMT-src-1.1.zip
dSFMT-src-1.1.tar.gz
Larger period 2132049-1 is supported. A bug about BIG ENDIAN machine is fixed. Some important bugs are fixed, but there is no influence to the outputs. Source codes were refactored. (2007/3/22)
1.0 dSFMT-src-1.0.zip
dSFMT-src-1.0.tar.gz
The first version. (2007/3/12)

If you have some trouble to download, try this page.

CPUs and compilers for SFMT optimized for SIMD

SIMD typeCPUsgcc optiongcc version
SSE2Intel: Pentium M, Pentium 4, core, core 2, etc
AMD: Athlon 64, Sempron, Turion 64, etc
see Wikipedia SSE2:CPUs supporting SSE2
-msse2 3.4 or later
AltiVecPowerPC G4, G5-faltivec3.3 or later

See also How to compile SFMT.

License

SFMT, as well as MT, can be used freely for any purpose, including commercial use. See LICENSE.txt for detail.

.

Back to Mersenne Twister Home Page


*1 This work is supported in part by JSPS Core-to-Core Program No. 18005: "New Developments of Arithmetic Geometry, Motive, Galois Theory, and Their Practical Applications."
This work is also partially supported by JSPS Grant-in-Aid for Scientific Research No. 16204002, No. 19204002 and No. 18654021.