gakushin logo
SFMT logo

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

English Version

最新情報

リンク

SFMT について

SFMTは2006年に、 松本眞教授とその指導学生の 斎藤睦夫によって、 開発された新しいタイプのメルセンヌ・ツイスタです。アルゴリズム はMCQMC 2006 で報告されました。 MCQMC2006 の会議録に論文が掲載されています。 (文献情報は、松本先生の 関連論文のページを参照してください。) SFMTは線形フィードバックシフトレジスタ式擬似乱数生成器で、 一度に128ビットの擬似乱数を生成するようになっています。 SFMTは最近のCPUの多段階パイプラインやSIMD といった並列処理能力を考慮して設計されています。 32ビットおよび64ビットさらに倍精度浮動小数点での出力もサポートしています。

SFMTは多くの計算機環境において、 MTよりも高速であることが期待出来ます。 乱数生成速度だけではく、 vビット精度の次元均等分布性においても改善が見られます。 また、 零超過状態からの回復もMTよりずっと高速です。 詳細については、 斎藤の修士論文(英文)を参照してください。

SFMTの実装であるSFMT19937は、以下の三つの環境でコンパイルできます。

  1. SIMD命令なしの標準C環境
  2. インテルのSSE2を備えたCPUとその機能をサポートするC コンパイラのある環境
  3. AltiVec命令を備えたCPUとその機能をサポートするCコンパイラのある環境

それぞれの環境において、SFMT はMTより高速でした。 速度比較(英文)を参照してください。

SFMT の均等分布次元の表を掲載しました。32bit64bitです。

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

このプログラムは2007年1月31日に一般に公開されました。 それで、いくつかバグがあるかも知れません。 バグ報告、その他ご意見などありましたら、saito アットマーク math.sci.hiroshima-u.ac.jp および m-mat アットマーク math.sci.hiroshima-u.ac.jp までメールしてください。

versionarchivechanges
new! 1.4.1 SFMT-src-1.4.1.zip
SFMT-src-1.4.1.tar.gz
Dirk Steenpass さんから報告された MSC コンパイル時の error を修正しました。 (2013/12/19)
1.4 SFMT-src-1.4.zip
SFMT-src-1.4.tar.gz
SFMTの内部状態を構造体で持つように変更しました。 関数名とマクロ名はsfmt_またはSFMT_で始まるように変更しました。 このバージョンはSFMT-jumpで使用するために作成されました。 ALTIVEC と BIGENDIAN は一切テストしていません。 (テスト環境がなくなりました)(2012/6/28)
1.3.3 SFMT-src-1.3.3.zip
SFMT-src-1.3.3.tar.gz
コンパイラのワーニングを避けるために、SSE2 や ALTIVEC が指定されたときに do_recursion 関数をコンパイルしないようにしました。 (2007/10/6)
1.3.2 SFMT-src-1.3.2.zip
SFMT-src-1.3.2.tar.gz
to_res53_mix と genrand_res53_mix のバグを修正しました。 (2007/8/20)
1.3.1 SFMT-src-1.3.1.zip
SFMT-src-1.3.1.tar.gz
MSC でコンパイルエラーになるバグを修正しました。 32 bit擬似乱数から53bit精度doubleを生成するto_res53_mix()と genrand_res53_mix()を追加しました。 gcc の最適化オプションを -O9 から -O3 に変更しました。 MSC の __forceinline オプションを追加しました。 (2007/8/12)
1.3 SFMT-src-1.3.zip
SFMT-src-1.3.tar.gz
周期 2216091-1 をサポートしました。 BIG ENDIAN に関するバグを修正しました。 並列生成する方のために、パラメータのデータを追加しました。 OSX 以外のOSで AltiVec を使うことを考慮しました。 (2007/6/2)
1.2 SFMT-src-1.2.zip
SFMT-src-1.2.tar.gz
2607-1 から 2132049-1 までの様々な周期 をサポートしました。ソースファイルをまとめました。vec_permの第二引数 の型が間違ってましたが、正しくキャストしました。(2007/3/1)
1.1 sfmt19937src-1.1.zip
sfmt19937src-1.1.tar.gz
周期保証方法が定数から関数に変更されました。 Makefileとドキュメントが変更されました。(2007/1/31)
1.0 sfmt19937src-1.0.zip
sfmt19937src-1.0.tar.gz
初版

ダウンロードがうまくいかない時は、こちら のページからやってみてください。

Double precision SIMD-oriented Fast Mersenne Twister (dSFMT)

dSFMT の開発目的は整数から浮動小数点数への変換のコストを避けることにあります。 dSFMT は IEEE Standard for Binary Floating-Point Arithmetic (ANSI/IEEE Std 754-1985) 形式の倍精度浮動小数点擬似乱数を直接生成します。 したがって、dSFMT は IEEE 754 形式の倍精度浮動小数点数を使用する CPU でしか利用出来ません。

dSFMT は整数の出力をサポートしません。dSFMT がサポートするのは [1, 2), [0, 1), (0, 1], (0, 1) の範囲に分布する倍精度浮動小数点擬 似乱数です。また、2607-1 から 2216091-1 ま での様々な周期をサポートします。(dSFMT ver. 2.1 は 2521-1 から 2216091-1 までの様々な周期をサポート します。)

このプログラムは2007年3月12日に一般に公開されたばかりです。 いくつかバグがあるかも知れません。 バグ報告、その他ご意見などありましたら、 saito アットマーク(@) math.sci.hiroshima-u.ac.jp および m-mat アットマーク(@) math.sci.hiroshima-u.ac.jp までメールしてください。 片方をCCにするなどして、二人宛てにしてくださると、 少しこちらの手間が省けます。

dSFMT のアルゴリズムは、このページでコードが公開された後、 MCQMC 2008 で発表されました。そのときには、主に dSFMT ver. 2.0 に ついて説明しました。 これが発表に使った スライド(PDFファイル) です。 MCQMC 2008 の会議録が出版されました。

versionarchivechanges
new! 2.2.3 dSFMT-src-2.2.3.zip
dSFMT-src-2.2.3.tar.gz
nmake での make が少し楽になるように少しだけ Makefile を修正しました。 (2013/12/19)
2.2.2 dSFMT-src-2.2.2.zip
dSFMT-src-2.2.2.tar.gz
Visual C++ 2012 でコンパイルエラーになる部分を修正しました。 (2013/9/17)
2.2.1 dSFMT-src-2.2.1.zip
dSFMT-src-2.2.1.tar.gz
AltiVec 用のシフト定数の定義を変更しました。 これまでの書き方はAltiVecの仕様に反していました。 (2013/2/21)
2.2 dSFMT-src-2.2.zip
dSFMT-src-2.2.tar.gz
SSE2 用の定数の初期化を変更しました。 dSFMT-common.h を作成しました。 このバージョンは dSFMT Jump で使用出来ます。 (2012/6/29)
2.1 dSFMT-src-2.1.zip
dSFMT-src-2.1.tar.gz
サポートする周期が2521-1 から 2216091-1 になりました。 dsfmt_genrand_uint32 で unsigned int の出力をサポートしました。 dSFMTは浮動小数点用の擬似乱数生成器ですが、大量の浮動小数点数と 少量の整数を必要とする時に、少量の整数のために別の擬似乱数生成器 を用意する不便さを解消するためです。 (2009/4/18)
2.0 dSFMT-src-2.0.zip
dSFMT-src-2.0.tar.gz
漸化式が変更されました。サポートする周期が変更されました。 (長い周期については現在パラメータを検索中です、そのうち追加 されるはずです。) 漸化式が変更された結果、出力列もまるで違っ たものになっています。生成速度が改善されました。初期化チェッ ク用の変数は、cygwinでエラーを起こすので削除しました。いまの ところサポートしている周期は、2521-1 から 219937-1 です。dSFMT 2.0 はより高速な生成を目標に 開発されました。dSFMT ver. 1.xx に本質的な問題が発見されたわ けではありません。1.xx を使い続けても問題はありません。 (2008/8/26)
1.3 dSFMT-src-1.3.zip
dSFMT-src-1.3.tar.gz
C 言語の構造体を使用するようにしました。 LITTLE ENDIAN のCPUをBIG ENDIANと判定してしまうバグを修正しました。 関数名は頭にdsfmt_を付けるように変更しました。 が、古い名前も有効です。マクロ名も変更しました、こちらは古い名前は無効です。 dSFMT.c と dSFMT.hをインクルードするユーザプログラムは、別々に コンパイルしてリンクすることが(以前から)出来ますが、 今回の構造体バージョンからは、dSFMT.hをインクルードするときは、 dSFMT.c をコンパイルしたときと同じ DSFMT_MEXP を指定して コンパイルする必要があります。 (2008/2/28)
1.2.1 dSFMT-src-1.2.1.zip
dSFMT-src-1.2.1.tar.gz
dSFMT.c に #include <alitvec.h>を追加しました。 (2007/8/29)
1.2 dSFMT-src-1.2.zip
dSFMT-src-1.2.tar.gz
注意:下記理由により dSFMT.xxx.out.txt ファイルが変更されました。 test.c で、printf 関数のdoubleの精度指定が間違っていました。 長い周期 2216091-1 がサポートされました。 gcc コンパイラの最適化オプションが -O9 から -O3 に変更されました。 OSX 以外のOS用のAltiVecのパラメータがサポートされました。 OSX 以外のOS用のgccのコンパイルオプションがサポートされました。 BSD用に howto-compile.html内のsample2 のコードが修正されました。 周期保証コードが少しスマートになりました。 BORLANDC と Visual Studio のinline指定をサポートしました。 (2007/8/22)
1.1 dSFMT-src-1.1.zip
dSFMT-src-1.1.tar.gz
2132049-1 という長い周期がサポートされました。 BIG ENDIAN マシンでチェックがエラーになるというバグが修正されました。 いくつか重要なバグが修正されましたが、 出力には影響がないはずです。 ソースコードにリファクタリングがなされました。 (2007/3/22)
1.0 dSFMT-src-1.0.zip
dSFMT-src-1.0.tar.gz
The first version. (2007/3/12)

うまくダウンロード出来ない時は、 こちらのページからダウンロードしてください。

SIMDに最適化されたSFMTを使えるCPUとコンパイラ

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

コンパイルの仕方(英文)も見てください。

License

MTと同様に、SFMTは商用利用を含むどんな目的にも自由に使用することができます。 詳細については、LICENSE.txt を見てください。 これは修正BSDライセンスです。

.

メルセンヌ・ツイスタのページへ。


*1 この研究は日本学術振興会先端研究拠点事業の補助を受けて行われています。No. 18005: "数論幾何・モチーフ理論・ガロア理論の新展開と、その社会的実用"
この研究は日本学術振興会科学研究費の補助も受けています。 No. 16204002, No. 19204002, No. 18654021.