疑似乱数生成器 spiegel-im-spiegel/mt

no extension

Mersenne Twister とは松本眞・西村拓士両氏によって1996年に発表された擬似乱数生成アルゴリズムである。 他の擬似乱数生成アルゴリズムと比べて以下の特徴があるそうだ。

  • 従来の様々な生成法の欠点を考慮して設計されています
  • 従来にない長周期, 高次元均等分布を持ちます(周期が $2^{19937}-1$ で、623次元超立方体の中に 均等に分布することが証明されています)
  • 生成速度がかなり速い
  • メモリ効率が良い
via Mersenne Twister とは?

特に2番目が重要で,モンテカルロ法などの科学技術計算に向いている。 Ruby などの一部のプログラミング言語では標準の疑似乱数生成器として組み込まれているらしい。

spiegel-im-spiegel/mtMersenne Twister のオリジナルコード(C/C++)を pure Go で書き直したものである。

Build Status GitHub license GitHub release

spiegel-im-spiegel/mt の特徴は以下の通り。

  • math/rand 互換で rand.Rand のソースとして利用できる
  • goroutine-safe な構成にできる(mt.PRNG 型を利用した場合)

mt/mt19937.Source の機能

mt/mt19937 パッケージは 64bit版 Mersenne Twister を元に pure Go で書き直したものである。

mt/mt19937.Source はそのまま疑似乱数生成器として使える。 たとえば以下のように記述する。

import (
    "fmt"

    "github.com/spiegel-im-spiegel/mt/mt19937"
)

fmt.Println(mt19937.NewSource(19650218).Uint64())
//Output:
//13735441942630277712

提供するメソッドは以下の通り。

メソッド 機能
Source.Seed(int64) 乱数のシードをセットする
Source.SeedArray([]uint64) 乱数のシード(配列)をセットする
Source.Uint64() uint64 乱数として範囲 $[0, 2^{64}-1]$ の整数値を生成する
Source.Int63() int64 乱数として範囲 $[0, 2^{63}-1]$ の整数値を生成する
Source.Real(int) float64 乱数として浮動小数点数値を生成する

Source.Real() 関数の引数による乱数の出力範囲は以下の通り。

引数 生成範囲
1 範囲 $[0, 1)$ の浮動小数点数値
2 範囲 $(0, 1)$ の浮動小数点数値
上記以外 範囲 $[0, 1]$ の浮動小数点数値

なお mt/mt19937.Source は goroutine-safe ではないので goroutine 間でインスタンスを共有できない。

math/rand と組み合わせる

mt/mt19937.Sourcerand.Rand のソースとして利用するには以下のように記述すればよい。

import (
    "fmt"
    "math/rand"

    "github.com/spiegel-im-spiegel/mt/mt19937"
)

fmt.Println(rand.New(mt19937.NewSource(19650218)).Uint64())
//Output:
//13735441942630277712

これで rand.Rand が提供するメソッドはすべて使える。 ただし rand.Rand も goroutine-safe ではないので,取り扱いにはやはり注意が必要である。

mt.PRNG と組み合わせる

mt/mt19937.Source 型を mt.PRNG 型と組み合わせることで goroutine-safe な構成にできる。 たとえばこんな感じに記述できる。

package main

import (
	"sync"
	"time"

	"github.com/spiegel-im-spiegel/mt"
	"github.com/spiegel-im-spiegel/mt/mt19937"
)

func main() {
	wg := sync.WaitGroup{}
    prng := mt.New(mt19937.NewSource(time.Now().UnixNano()))
	for i := 0; i < 1000; i++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			for i := 0; i < 10000; i++ {
				prng.Uint64()
			}
		}()
	}
	wg.Wait()
}

mt.PRNG 型は mt/mt19937.Source のラッパーになっていて rand.Rand と組み合わせることも可能だが, rand.Rand の内部構造の問題で goroutine-safe にならない。 ご注意を。

io.Reader 互換の疑似乱数生成器

mt.PRNG のインスタンスから mt.Reader 型のインスタンスを生成できる。 こんな感じに記述できる。

package main

import (
	"fmt"
	"sync"
	"time"

	"github.com/spiegel-im-spiegel/mt"
	"github.com/spiegel-im-spiegel/mt/mt19937"
)

func main() {
	wg := sync.WaitGroup{}
	prng := mt.New(mt19937.NewSource(time.Now().UnixNano()))
	for i := 0; i < 1000; i++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			r := prng.NewReader()
			buf := [8]byte{}
			for i := 0; i < 10000; i++ {
				ct , err := r.Read(buf[:])
				if err != nil {
					return
				}
                fmt.Println(binary.LittleEndian.Uint64(buf[:ct]))
			}
		}()
	}
	wg.Wait()
}

mt.Reader 型は io.Reader インタフェースと互換性がある。 また mt.Reader インスタンスも goroutine-safe なので goroutine 間で共有可能である。

ライセンスについて

spiegel-im-spiegel/mt は MIT ライセンスで提供している。

オリジナルの Mersenne Twister コードは GPL または BSD ライセンスで提供されているが MIT ライセンスに書き換えてもいいらしい。

というわけで spiegel-im-spiegel/mt は MIT ライセンスで提供することにした。 ご利用はお気軽に。

参考図書

photo
プログラミング言語Go (ADDISON-WESLEY PROFESSIONAL COMPUTING SERIES)
Alan A.A. Donovan (著), Brian W. Kernighan (著), 柴田 芳樹 (翻訳)
丸善出版 2016-06-20
単行本(ソフトカバー)
4621300253 (ASIN), 9784621300251 (EAN), 4621300253 (ISBN), 9784621300251 (ISBN)
評価     

著者のひとりは(あの「バイブル」とも呼ばれる)通称 “K&R” の K のほうである。この本は Go 言語の教科書と言ってもいいだろう。

reviewed by Spiegel on 2018-10-20 (powered by PA-APIv5)

photo
数学ガール/乱択アルゴリズム
結城 浩
SBクリエイティブ 2011-02-25 (Release 2014-03-12)
Kindle版
B00I8AT1FO (ASIN)
評価     

工学ガール,リサちゃん登場!

reviewed by Spiegel on 2015-04-19 (powered by PA-API)